Dynamic three-value logic in decentralized time-critical domains

Share Embed


Descrição do Produto

The IEEE Sixth International Symposium on Autonomous Decentralized Systems, ISADS 2003, pp. 131-138, 9 – 11 April, 2003, Pisa, Italy

Dynamic Three-Value Logic in Decentralized Time-Critical Domains Marion G. Ceruti,* Ph.D., Senior Member, IEEE, Stuart H. Rubin, ** Ph.D., Senior Member, IEEE, Space and Naval Warfare Systems Center, San Diego, Code 24121, 53560 Hull Street, San Diego, CA 92152-5001, USA *Code 24121, Tel. (619) 553-4068, FAX (619) 553-5136, [email protected] **Code 27305, Tel. (619) 553-3554, FAX (619) 553-1130, [email protected]

Abstract This paper describes conceptual work in dynamic three-value logic with a view toward applications in decentralized time-critical domains, such as a sensor field. The completeness and computability of 3VLs also are discussed, including an algorithm to illustrate the use of heuristics. The military services deploy systems of heterogeneous sensors to detect and classify platforms. The paper provides a brief overview of the heterogeneous, decentralized sensor field used for military target classification as hostile, neutral or friendly. In an example, threevalue logic is used to characterize the movement of a ship through a sensor field in terms of relevance and conclusiveness of the aggregate of sensor information. The paper concludes with a discussion of directions for future research and development. Keywords – Data fusion, decentralized systems, heterogeneous systems, three-value logic, sensors, timecritical targets

The main application of this logic is the detection of military targets (e.g. ships, planes, missiles, etc.) that are moving in an autonomous, decentralized array of sensors. Each system has a three-value logic, based on three logical levels where “True” (T) occupies level 1, “Not applicable” (N) and “Inconclusive” (I) together occupy level 2, and “False” (F) occupies level 3. N.B. this could be framed as a four-value logic by counting separately N and I. We consider systems in which each target can occupy only one state of truth (e.g. either T, F, N or I) at any given time. This paper is organized as follows. Section 2 introduces basic concepts and characteristics of D3VL for the case of a single variable, and also the case of multiple variables. Section 3 discusses uncertainty and incompleteness in 3VLs. Section 4 describes heterogeneous sensors for target classification. Section 5 covers an example of the application of D3VL to decentralized systems. Section 6 concludes with a discussion of directions for future research.

2. Concepts in three-value logic 1. Introduction 2.1 Single-variable case The purpose of this study is to develop a framework in which scenarios and solutions for time-critical problems can be documented and tested, respectively. In this paper, the following questions are considered: • Why do we need three-value logic (3VL)? • What is the role of time dependence and why does this logic need to be dynamic (D3VL)? • What is the nature truth states that are neither not T or F? • What is the role of conditional probability in threevalue logic? • What is the definition of time criticality? • Are 3VLs amenable to heuristics to provide computational tractability? • How does three-value logic apply to autonomous decentralized systems?

A great deal of work has been done in the area of multi-valued logic. (See, for example, [5]). However, time dependence has not been addressed with regard to truth state changes. The dynamic three-value logic that we describe in this paper features three logical levels and four truth states of a system. This includes the T truth state (level 1) the F truth state (level 3) and a middle logical level that includes two truth states called N (not applicable) and I (inconclusive.) In some cases, the middle truth state can be a state of irrelevance or non-applicability, N. In other cases, the middle truth state, I, can be very relevant but not enough information is available to categorize the state as either T (level 1) or F (level 3).

Thus, for level 2, (the middle level) truth state, I, can be termed, “incomplete,” “in between,” “indecisive,” “inconclusive,” “indefinite,” or “ill defined.” Often, a system in truth state, I, will have some properties in common with another system in truth state, T, and other properties in common with a system in truth state, F. However, by definition, any system in truth state, I will not have enough properties in common with either to warrant categorization as either T or F. In dynamic three-value logic, T, F, N and I are timedependent truth states of a system at time, t. A system can occupy any one of these states as a function of time. For example, a variable that is not applicable (N) may become applicable but indefinite (I) as other variables on which it depends evolve in time. Truth state, I, can change to T or F when additional information is obtained that clarifies the situation. Alternately, it can remain stable in truth state, I, for any arbitrary length of time. In this system of logic, it is not possible to move directly from truth state, N, to either truth state, T, or F. However, the N -> F or the N -> T state transitions can be simulated by requiring the system to spend only an extremely small amount of time in truth state, I, smaller than the duration

D=0 Level 1

T D(t)

Level 2

N

Level 3

I F

of one CPU machine cycle. Figure 1. State diagram for dynamic 3VL With respect to logical level 2, consider the timedependent “distance” function, D(t), which is defined as the “distance” between truth state, N, which is a state of non-applicability, and the truth state, I, which is a state of relevance. D(t) is a measure of non-applicability or irrelevance. D(t) is related to a set of attributes that completely specifies the T and F states. This distance function also is called “the odds” and it pertains to the probability of a state change not happening, compared to the probability that it will occur. D(t) is defined in equation (1) and illustrated in figure 1. This figure also shows that dynamic three-value logic is actually a two-dimensional logic, with the logical levels, 1, 2, and 3, as one dimension, and D(t) as the other dimension.

(1) D(t) = (1/P(t)) – 1 P(t) is the time-dependent probability that a state change will occur as a function of specific variables that apply to the given situation. P(t) can be a conditional probability or a second-order probability. Consider the time-dependent state variable of a system Zt. Let P(Zt | Ct) be the probability that a system will occupy a particular state, Zt that is characterized by a specific set of values that correspond to time-dependent variables (Ct) that determine the state at time t. D(t) also can be written as follows. (2)

D(t) = P(Zt´ | Ct) / P(Zt | Ct)

where P(Zt´ | Ct) = 1- P(Zt | Ct). 2As D(t) approaches infinity, logical level 2 applies and the truth state assumes the quality of total nonapplicability. Any such N truth state will not have appropriate attributes to trigger T or F. For D(t) = 0, a system can have some attributes to qualify for T or F, but not enough to decide T or F conclusively. Therefore, truth state, I, applies, but we cannot make a definite classification as either T or F because an entity in the I state fails to meet minimum criteria to be in either truth state, T, or truth state, F. Let µ( Zt) be the truth state of the system, Zt. Equations (3) through (6) illustrate the behavior of D(t) as a function of µ( Zt): (3) D(t) = 0 if µ( Zt) = T (4) D(t) = 0 if µ( Zt) = F (5) D(t) = 0 if µ( Zt) = I (6) D(t) = P(Zt´ | Ct) / P(Zt | Ct) if µ( Zt) = N Examples illustrate the relationships between T, F, N and I. As example 1, consider the question, “Is your air squadron qualified for search and rescue (SAR)?” If you belong to a submarine unit, the N truth state applies and D(t) >> 0. If you plan to transfer from a surface unit to an air squadron tomorrow, D is not zero but close to zero such that D(t) ~ 0, because the question is becoming less and less irrelevant as time progresses. Suppose you belong to an air squadron that is not yet qualified to perform search and rescue, but is training to become qualified by passing a series of tests. Assume that, say, three out of six tests have been passed. Truth state, I, applies here, because the unit is partially but not totally qualified. D(t) = 0 but truth state, T, does not apply yet. One could argue that, strictly speaking, until a unit is totally qualified, it could be considered unqualified (i.e. truth state, F, applies), which is to revert to two-value logic.

However, this is not the most useful or practical approach for many situations because it ignores the time evolution of the unit toward a state of total qualification. It also is not useful for planning purposes. A commander may want to treat such a unit in training with a different protocol from one that is either totally trained or one that is neither trained nor in training for SAR. The SAR example cited above is analogous to some medical cases. As example 2, consider that some patients are difficult to diagnose as having a disease or not having it because telltale symptoms associated with the disease are observed but not certain critical and defining symptoms that determine the disease. (See, for example, [6].) Some patients in this category can persist in truth, I, indefinitely and never develop the disease, whereas others do. Here again, the medical protocol for treating patients in truth state, I, differs from that of patients in truth state, T, (i.e. having the disease) and also from that of patients in truth state, F, (i.e. clearly not having the disease.) Thus, in multiple domains, three-value logic can be more useful than the traditional two-value logic, in dealing with physically observable situations and their evolution. 2.2 The use of conditional probability in three-value logic Assume that system state, Zt, is determined by observable variables A, B, and C and that A and B are conditioned on C. For observable variables A, B, and C, and unknown system state, Zt, consider the following test for “I.” Rule 1: If A = T or B = T then µ( Zt) = T. Rule 2: If A = F and B = F then µ( Zt ) = F. Assume that P(A|C) and that P(B|C) are both close to 1 but not identically 1. What happens if C = T but A = F and B = F? In this case µ( Zt) = I. In some cases, truth state, I, can be characterized as follows: Given two conditions, 1 - P(A|C) not) may be in-

cluded if care is taken to avoid cyclic transformations. Such transformations may also be used to normalize the case of various words (e.g., the bus –> The bus). Expansion rules cannot be used for semantic translation because this would create a Type 0 instead of a Type 1 grammar, which is of course subject to the halting problem. (See, for example, [2].) The individual words are to be normalized syntactically prior to the application of any context-sensitive (syntactically normalized) contraction rules. An optional algorithm for spell checking can provide additional syntactic normalization. The essential procedural description of the algorithm follows. Note that stability can be attained by disabling union and differencing procedures and simply appending each new set of ordered pairs (singletons) as necessary.

1. Get a user specification in natural language (NL). 2. Unmark all fault descriptions to designate them as unvisited. 3. Syntactically normalize individual words (optionally including identity transformations and/or spell checking). 4. Iteratively apply context-sensitive contraction rules. 5. Use the case-sensitive hash table to generate a set of ordered pairs (singletons) that corresponds to the user specification. 6. Compute the percentage of ordered pairs (singletons) that the normalized specification has in common with each of the fault descriptions. Note that this percentage never exceeds unity. 7. WHILE the user does not signal an interrupt AND unvisited fault descriptions remain on the list, DO: Visit an unvisited fault description in non-increasing order of the percentage metric and mark it as visited. Echo the associated semantic tag to the user for confirmation. IF correct, THEN DO: Replace the fault description with that obtained by taking the union of itself with that of the specification. Save all changes, if any. RETURN the proper fault code. Otherwise, DO: Replace the fault description with that obtained by subtracting that of the specification from it. 8. Ask the user to rephrase the specification, or optionally save all changes (if any), THEN EXIT with failure. 9. GOTO step (1).

Figure 5. The AN/APG-68 Non-Conversational Algorithm

4. Heterogeneous, decentralized sensor field The field of sensors used by the U.S. military establishment evolved in a decentralized manner because different agencies, organizations and commands are, and historically have been, responsible for the development, installation, maintenance, and utilization of different sensor types. For examples, one organization may control satellite imaging whereas another is in charge of acoustic sensors. Still other organizations are concerned with electronic, electro-optic, and/or magnetic signals. Moreover, in the case of Naval ships, each ship has its own set of sensors over which the

ship’s captain exercises control and over which other higher-ranking officers in the chain of command exercise a more limited control if any. The U.S. Navy has evolved in a culture where each ship has been considered to be autonomous and self sufficient to a certain extent. This can be understood in historical terms because efficient, electronic communications and transportation techniques are relatively recent introductions into modern Navies. For centuries prior to modern informationexchange techniques, ships’ commanders used whatever information they could gather locally.

Today, the uses of this decentralized sensor field include platform tracking, classification, identification and targeting. Decentralization has two advantages. 1. It provides some administrative and programmatic independence for target types and ships. 2. It permits a network of platforms to exchange information and coordinate their maneuvers flexibly and with greater scalability than anything that would be possible with a single, centralized control platform [3]. This type of inter-platform data exchange and fusion forms the crux of network-centric warfare [3]. (See also, for example, [1].)

friendly). The “distance” function now becomes equation (11). (11)

D0(t) = 1 / P(H|G) – 1

where, P is a second order probability function.

5. Sensor-field application A common problem in the military is to determine classification (friendly, hostile, or neutral), and in some cases, the identity of a vessel given a sensor array that includes sensors with fixed geometry and a vessel track. Secondorder probability will be needed to solve this problem. In any case, we assume for simplicity that sensors, S1 and S2, are perfect with no errors. Let V be a vessel that we want to classify as friendly, hostile or neutral. The trajectory or track of vessel V is shown as a bold arrow in figure 6. This track is divided into five contiguous segments, depending on whether or not the vessel is within the detection range of one or both sensors. Each segment of the vessel’s track has a time interval that corresponds to the time it spends in that part of the track. The range of each sensor is symbolized in figure 6 by a circle for S1 and an oval for S2. As shown in figure 6, t0, t1, t2, t3, and t4 are the time intervals that the vessel spends when its track intersects the various regions of the sensor field. For example, t2 is the time interval the vessel spends simultaneously in the range of both sensors. For simplicity, we have assumed that the vessel proceeds along a geodesic. Suppose we need data from both S1 and S2 for a conclusive determination of V’s identity. If V is outside the ranges of S1 and S2, the truth state of the system is N because neither sensor can detect the vessel. The truth states are indicated in figure 6 by dotted lines. During time intervals t1 and t3 the vessel is detected by only one of the two sensors and some data are received, but because we need data from both sensors, the data from only one sensor are insufficient to make a positive determination of the vessel’s identity. However, this scenario is amenable to D3VL. Therefore, the system can assume a truth state of “I” during time intervals t1 and t3. During time interval t2, the vessel’s identity can be determined because vessel V will enter a region in which data from both sensors are available simultaneously. Let G be the event that the trajectory of the V is along the straight-line path depicted in figure 6. Let H be the event of a positive determination (which means that the classification is known, not that the vessel is necessarily

Figure 6. Vessel V moving in a two-sensor field (S1 and S2) with truth states N, I, T or F

6. Directions for future research More work is needed in this area, especially in the military domain. The results for the two-sensor field can be generalized to a multi-sensor field, using various combinations of AND and OR to accommodate different fusion algorithms. A more efficient system based on D3VL can be envisioned than anything we have today. For example, automated sensor data outputs can be stored electronically in databases which can feed fusion algorithms based on D3VL. The output of the algorithms together with current sensor status (e.g. mode, uncertainty, availability, etc.) and other information can contribute to a more comprehensive picture of the dynamic nature of the battle space. Using this output, parallel processors can compute and track state changes for multiple platforms and issue alerts based on predictions of the most likely of time-critical events. Perhaps the most challenging aspect of applications of D3VL is to develop a model for the probability function, P(t), in equation (1), and to select features of observable variables that are most likely to be able to predict related events that trigger truth state changes.

Acknowledgments The authors thank the Defense Advanced Research Projects Agency for financial support, Dr. I.R. Goodman for helpful discussions on logic, and the anonymous reviewers for their careful and detailed, reviews of the paper. This work was produced by U.S. government employees as part of official duties and is no copyright subsists therein. It is approved for public release with an unlimited distribution.

References [1] M.G. Ceruti, “Mobile Agents in Network-Centric Warfare,” Institute of Electronics Information and Communication Engineers Transactions on Communications, Tokyo, Japan., vol. E84-B, no. 10, pp. 2781-2785, Oct. 2001. [2] A.J. Kfoury, R.N. Moll and M.A. Arbib, A Programming Approach to Computability, New York, N.Y. SpringerVerlag, Inc., 1982.

View publication stats

[3] S. Julier and J.K. Uhlman, “General Decentralized Data Fusion with Covariance Intersecction (CI),” Chapter 12 in Handbook of Multisensor Data Fusion, D.L. Hall, and J. Llinas, eds., CRC Press, Boca Raton, 2001. [4] S.H. Rubin, “A Heuristic Logic for Randomization in Fuzzy Mining,” J. Control and Intelligent Systems, vol. 27, no. 1, pp. 26-39, 1999. [5] N. Rescher, Multivalued Logic, 1968. [6] M. Ulieru, O. Cuzzani, S. H. Rubin and M. G. Ceruti, “Application of Soft Computing Methods to the Diagnosis and Prediction of Glaucoma,” Proceedings of the 2000 IEEE International Conference on Systems, Man and Cybernetics, pp. 3641-3645, Nashville, TN, USA, October 8-11, 2000. [7] V.A. Uspenskii, Gödel’s Incompleteness Theorem, translated from Russian. Moscow: Ves Mir Publishers, 1987.

Dr. Marion G. Ceruti is a scientist in the Advanced Concepts and Engineering Division of the Command and Control Department at the Space and Naval Warfare Systems Center, San Diego. She received the Ph.D. in 1979 from the University of California at Los Angeles. Dr. Ceruti's professional activities include information systems research and analysis for command and control decision-support systems, sensor fusion, and research management. Dr. Ceruti is the author of over 65 journal articles, conference proceedings, monographs and book chapters on various topics in science and engineering. She is a senior member of the IEEE and a member of the IEEE Computer Society, the Armed Forces Communications and Electronics Association (AFCEA), the American Chemical Society, the Acoustical Society of America, and the New York Academy of Sciences. Dr. Stuart H. Rubin is a senior scientist at the Space and Naval Warfare Systems Center, San Diego (SPAWARSYSCEN). Prior to joining the center, he was an associate professor of computer science at Central Michigan University in Mt. Pleasant, MI. He received the Ph.D. degree from Lehigh University, Bethlehem, PA. Dr. Rubin’s research interests include fuzzy information mining, intelligent (Internet-based) tutoring, knowledgebased and knowledge-discovery systems, and software reuse. He is the author of over 110 publications. Dr. Rubin is a senior member of the IEEE, AFCEA, the American Association for the Advancement of Sciences, the North American Fuzzy Information Processing Society, the New York Academy of Sciences and several other scientific societies.

Lihat lebih banyak...

Comentários

Copyright © 2017 DADOSPDF Inc.