Daniel G. Schwartz
Department of Computer Science, Florida State University, Tallahassee, USA.
DOI: 10.4236/jcc.2026.148001   PDF    HTML   XML   5 Downloads   40 Views   Citations

Abstract

This paper offers a new concept of possibility as an alternative to the concept originally introduced by L.A. Zadeh in 1978. This new version was inspired by the original but, formally, has nothing in common with it other than that they both adopt the same interpretation of the logical connectives. Moreover, rather than seeking to provide a general notion of possibility, this focuses specifically on the possibility of a real-world event. An event is viewed as having prerequisites that enable its occurrence and constraints that may impede its occurrence, and the possibility of the event is computed as a function of the probabilities that the prerequisites hold and the constraints do not. This version of possibility might appropriately be applied to problems of planning. When there are multiple plans available for achieving a goal, this theory can be used to determine which plan is most possible, i.e., easiest or most feasible to complete. It is speculated that this model of reasoning correctly captures normal human reasoning about plans. The theory is elaborated and an illustrative example for vehicle route planning is provided. There is also a suggestion of potential future applications.

Keywords

Possibility, A Real-World Event, Street Network

Share and Cite:

1. Introduction

Possibility theory was introduced by Lotfi A. Zadeh in 1978 [1]. The essential idea was that, in a manner to explained in the following, a fuzzy set membership function can be interpreted as a possibility distribution. This led to the offering of possibility theory as an alternative to probability theory as a formulation of uncertainty. As stated by Zadeh, a possibility value can be interpreted as a measure of “the ease” with which an event can occur. This contrasts with the notion of a probability value, which measures the likelihood that the event will occur.

That paper caught the attention of numerous researchers who proceeded to advance this theory. Prominent among these are the French mathematicians, Didier Dubois and Henri Prade, who produced a book on this subject [2] and over the years have published many papers on this topic. Related works have also appeared in an early collection edited by Ronald Yager [3], and in the more recent collection by Paul Wang [4], both of whom have helped to advance the theory. There are many others. Zadeh himself returned to the topic several times, and the subject now enjoys a rich literature.

Two more recent papers are [5] and [6]. These review most of what has been accomplished to-date and can be taken as representing the current state of the art on this topic. The details of that approach are well-documented in the cited references and will not be repeated here. But briefly, the essential idea proposed by Zadeh is that a fuzzy membership function can be interpreted as a possibility distribution under the following semantic reinterpretation.

If one says that a particular person has a 0.7 degree of membership in the collection of tall people, this can be interpreted as saying that there a 0.7 degree of possibility for assigning the attribute “tall” to that person. Accordingly, the fuzzy set membership function can be interpreted as a possibility distribution. This notion of possibility can be extended to real-world events, where the possibility degree of the event is taken as a measure of the “ease” with which that event may occur, or more exactly, the degree with which the attribute “easy to occur” may be assigned to that event.

Whereas the present paper offers a new way of looking at the concept of possibility, it in no way usurps the original. It only presents an alternative. However, it does address an inherent weakness in that theory—this being that the notion of possibility provided in that version is purely subjective. This is because, in general, there are no objective methods for determining the values of a fuzzy membership function.

The subjectivity of this notion of possibility is mentioned by Zadeh on p. 7 of [1]:

“since our intuition concerning the behaviour of possibilities is not very reliable, a great deal of empirical work would have to be done to provide us with a better understanding of the ways in which possibility distributions are manipulated by humans. Such an understanding would be enhanced by the development of an axiomatic approach to the definition of subjective possibilities—an approach which might be in the spirit of axiomatic approaches to the definition of subjective probabilities.”

I believe that this statement can be taken as an implicit acknowledgment that the given notion of possibility is inherently subjective.

This may be contrasted with the standard notion of probability, which affords both subjective and objective methods for determining a probability. The objective methods comprise the methods of statistical samplings. If one wants to know, for example, the probability that a newborn child will suffer from autism, one can perform a sampling of children and find, for example, that this occurs in 1 out of every 50 children, in which case the probability can be given as 1/50 = 0.02. There is no similar procedure for possibility. This, I will speculate, is the reason that, while possibility theory is now quite advanced, there have been few practical applications.

The version of possibility being introduced here stands in contrast with the original in that, by basing a notion of possibility on the concept of probabilities for prerequisites and constraints, this can provide an objective method for computing a possibility degree. While one still has the option of employing subjective probabilities if desired, these probabilities can be determined objectively as long as the relevant data can be obtained. For this reason, this new concept should be more amenable to real-world applications.

In comparison with the original version, this approach does not employ fuzzy sets. Accordingly, while this work has been inspired by the works of Zadeh and the others, it comprises a completely different way of looking at the concept of possibility.

Having said this, however, it happens that the present system does share with fuzzy sets theory the interpretation of the logical “not”, “and”, and “or”, respectively, as the arithmetic 1-, min, and max operations. The use of these operators in fuzzy systems has its origin in the 1965 paper by Zadeh [7] and nowadays has widespread acceptance as providing an intuitively plausible model of natural human reasoning with imprecise concepts. They are being used in this paper in this same spirit.

It is worth noting that the use of these operators inspired a new research thread that led to generalizations that came be known as triangular norms or t-norms, having dual operators known as t-conorms. These serve respectively as alternative formulations of the logical “and” and “or”. Two books on this topic are [8] and [9], and a brief summary overview can be found at [10]. Such operators could be used in the present system in place of the min and max operators if this were deemed appropriate for a given application. However, this excludes the probabilistic versions of these operations, inasmuch as those operators as not suitable in the present context and are in fact in conflict with the basic notion of possibility. This issue is discussed more extensively in the following Section 8.

Moreover, this interpretation of the logical connectives is by no means unique to fuzzy sets theory. Logics of this type have been studied extensively in the literature on multi-valued logics. The earliest discussion of this kind of logic may attributed to Jan Łukasiewicz, whose formulation is presented in [11], p. 337, as the system $L_{{\aleph }_1}$ . The original publications are the 1930 papers [12] and [13].¹ This logic, as described in [11], provides the same interpretations of the logical connectives as in the present work and it additionally provides an interpretation for the implication connective $\to$ . Thus, the logic being used here may be viewed as a subsystem of $L_{{\aleph }_1}$ and, for want of a better term, will be referred to simply as the multivalent logic.

Real-world events are herein regarded as being context dependent, where the prerequisites and constraints comprise the context. A core feature of this work is that it introduces a function Poss ($E$ ) for evaluating the possibility of an event $E$ . The value returned by this function is intended to be taken as a measure of the feasibility or ease or occurrence of $E$ and not as a measure of its likelihood or potential frequency.

The following Section 2 offers an intuitive rationale for this approach in terms of a simple example. Section 3 presents a precise formalization. Section 4 continues the example presented in section 2, adding a new feature. Section 5 expands the formalism presented in Section 3 to encompass this added feature. A key issue addressed here is how to determine when two contexts are equivalent. Section 6 considers the case of more complex events, where the possibility of an event depends on the possibilities of precursor events. Section 7 presents an illustration of these ideas in a simple example involving vehicle routing via waypoint navigation. Section 8 compares the alternative formulation using probability theory. Section 9 suggests prospects for future applications. Section 10 provides concluding remarks. An appendix presents the results of a software implementation of the system and provides a link to the current version of the software.²

2. Intuitive Rationale

To illustrate the core ideas, suppose that ABC Corporation wishes to develop a new product line and needs to build a new factory as well as acquire additional employees. Let us assume that this requires raising sufficient capital to finance the project and, in addition, requires the availability of suitable new employees. Then “capital” and “employees” are prerequisites. It is proposed to compute the degree of possibility for the new product line as a function of the probability that ABC Corporation will be able to obtain the necessary capital and employees, to wit,

$\text{Poss}\left(\text{new\_product}\right)=\text{min}\left[\text{Prob}\left(\text{capital}\right),\text{Prob}\left(\text{employees}\right)\right]$ (1)

where Prob is a standard probability measure such as given by the well-known Kolmogorov axioms, cf. [16]. As noted previously, the min operation represents the logical “and” in the multi-valent logic.

While the probabilities in this example might not lend themselves to evaluation by statistical samplings, it is clear that in many applications they would. Consider for example the following weather prediction from a local newspaper [17]:

“Severe storms possible ahead of Christmas Day”

“There is a possibility of 2 - 3 inches of rain.”

These possibilities are based on probabilistic models involving such factors as temperature, humidity, cloud formations, and wind currents.

In this spirit, the proposed approach uses the methods of probability theory to determine the likelihood that the prerequisites will be satisfied and then uses the multivalent logic to give the degree of possibility for the event. Note that, in this example regarding ABC Corporation, we are here considering only the possibility that they may choose to develop the new product line, or following Zadeh, the “ease” with which this might occur, and not the probability that they will actually do so. This idea of interpreting a possibility degree for an event as a “degree of ease” with which the event may occur is discussed at some length on pages 8 - 9 of [1].

Now suppose that ABC Corporation has learned that there may be environmental issues that could interfere with their plans to build a new factory on a particular site. This would be a constraint. In this case, the foregoing computation becomes

$\begin{array}{c}\text{Poss}\left(\text{new\_product}\right)=\text{min}[\text{Prob}\left(\text{capital}\right),\text{Prob}\left(\text{employees}\right),\\ \text{Prob}\left(\neg \text{environmental\_issue}\right)]\end{array}$ (2)

or equivalently

$\begin{array}{c}\text{Poss}\left(\text{new\_product}\right)=\text{min}[\text{Prob}\left(\text{capital}\right),\text{Prob}\left(\text{employees}\right),\\ 1-\text{Prob}\left(\text{environmental\_issue}\right)]\end{array}$ (3)

using the probability theory representation of the logical “not”. In effect, $1-\text{Prob}\left(\text{environmental\_issue}\right)$ measures the degree to which the constraint “environmental_issue” is mitigated. Note that this amounts to regarding the mitigation of the constraint as a precondition. In general, any constraint $c$ can be construed as specifying a corresponding precondition having the form $\neg c$ .

These examples illustrate an intuitively plausible means for working with conjunctions of contextual elements (prerequisites and constraints). For a further example, involving disjunction and using the multivalent “or”, suppose that ABC Corporation has two employees, Jack and Jill, that they believe could be effective managers of their new factory, so that the success of their new enterprise depends on at least one of these people being interested. This can be expressed as

$\begin{array}{c}\text{Poss}\left(\text{new\_product}\right)=\text{min}[\text{Prob}\left(\text{capital}\right),\text{Prob}\left(\text{employees}\right),\\ 1-\text{Prob}\left(\text{environmental\_issue}\right)\\ \text{max}\left[\text{Prob}\left(\text{Jack}\right),\text{Prob}\left(\text{Jill}\right)\right]]\end{array}$

But now suppose they have recently learned that Jack has health issues that might make him unavailable. Then the formula for the event can be written as

$\begin{array}{c}\text{Poss}\left(\text{new\_product}\right)=\text{min}[\text{Prob}\left(\text{capital}\right),\text{Prob}\left(\text{employees}\right),\\ 1-\text{Prob}\left(\text{environmental\_issue}\right)\\ \text{max}\left[\text{Prob}\left(\neg \text{Jack\_unavailable}\right),\text{Prob}\left(\text{Jill}\right)\right]]\end{array}$ (4)

or

$\begin{array}{c}\text{Poss}\left(\text{new\_product}\right)=\text{min}[\text{Prob}\left(\text{capital}\right),\text{Prob}\left(\text{employees}\right),\\ 1-\text{Prob}\left(\text{environmental\_issue}\right)\\ \text{max}\left[1-\text{Prob}\left(\text{Jack\_unavailable}\right),\text{Prob}\left(\text{Jill}\right)\right]]\end{array}$ (5)

From a purely logical standpoint there is no difference between regarding a constraint as such and regarding the semantic negation of the constraint as a prerequisite, for which reason the very consideration of constraints might seem superfluous. Such do play a role, however, as a means of making the constraints explicit in the context of the event. For example, the negated constraint $\neg \text{Jack\_unavailable}$ might have been expressed as the prerequisite $\text{Jack\_unavailable}$ , but taking the former approach emphasizes the fact that Jack’s possible unavailability might be an issue.

Since probabilities are always in the range $\left[0,1\right]$ , so also will be the values returned by the foregoing applications of 1-, min and max, and therefore also the values of the function Poss. These values will be referred to as possibility degrees.

3. Formalization

These considerations motivate the following formal definitions. For an event $E$ , any proposition $p$ can serve as a prerequisite, and any proposition $c$ can serve as a constraint. Let us define the contextual constructs for event $E$ by:

1) If $p$ is a prerequisite for $E$ , then $p$ is a contextual construct for $E$ .

2) If $c$ is a constraint for $E$ , then $\left(\neg c\right)$ is a contextual construct for $E$ .

3) If $C_1$ and $C_2$ are contextual constructs for $E$ , then ($C_1\wedge C_2$ ) is a

contextual construct for $E$ .

4) If $C_1$ and $C_2$ are contextual constructs for $E$ , then ($C_1\vee C_2$ ) is a

contextual construct for $E$ .

5) Nothing is a contextual construct for $E$ except as required by the items 1 through 4.

Outermost surrounding parentheses will be omitted when not required for disambiguation. A contextual construct either of the form $p$ where $p$ is a prerequisite or of the form $\neg c$ where $c$ is a constraint will be an atomic contextual construct.

Given an event $E$ , let us define the possibility valuation $v$ for contextual constructs for $E$ by:

1) If $C$ is an atomic contextual construct for $E$ , then $v\left(C\right)=\text{Prob}\left(C\right)$ .

2) If $C$ is of the form $\left(C_1\wedge C_2\right)$ where $C_1$ and $C_2$ are contextual constructs for $E$ , then $v\left(C\right)=\text{min}\left(v\left(C_1\right),v\left(C_2\right)\right)$ .

3) If $C$ is of the form $\left(C_1\vee C_2\right)$ where $C_1$ and $C_2$ are contextual constructs for $E$ , then $v\left(C\right)=\text{max}\left(v\left(C_1\right),v\left(C_2\right)\right)$ .

Note that the method for determining Prob($C$ ) for an atomic construct $C$ can be either objective or subjective, where an objective method would comprise a calculation based on statistical samplings of relevant data, and a subjective method would be the result of a judgement by the system’s designer. For the purposes of this model it is assumed that the methods for evaluating Prob($C$ ) for the various atomic contextual constructs $C$ are independent one another in the sense that, for any two such constructs $C_1$ and $C_2$ , the method for evaluating Prob($C_1$ ) has no impact on the value Prob($C_2$ ) and, vice versa, the method for evaluating Prob($C_2$ ) has no impact on the value Prob($C_1$ ). This assumption seems reasonable from the standpoint of practical applications, and is made in the interests of mathematical economy. Allowing for interactions among evaluation methods would add another layer of mathematical complexity that is beyond the scope of this work.

Let us say that a contextual construct for an event $E$ is complete if it is considered to be a full description of the relevant context for $E$ in terms of the event’s prerequisites and constraints. Then if $C$ is a complete contextual construct for $E$ , set

$\text{Poss}\left(E\right)=v\left(C\right)$

Note that this notion of completeness for contextual constructs is fundamentally intuitive and inherently ambiguous inasmuch as it depends on a human user’s perception of the relevant situation. This condition is unavoidable. There can be no systematic procedure for determining whether a construct is complete inasmuch as this determination is always application specific, and it is impossible to anticipate every possible type of application. Moreover, for any particular application, one person may consider a different set of prerequisites and constraints than another as being necessary. In effect, this introduces a new element of subjectivity at the meta level. This subjectivity notwithstanding, however, the notion serves a useful purpose, once a particular conceptual construct has been chosen and agreed upon.

Let us now illustrate this formalism with a return to the foregoing examples.

4. Examples Revisited

For a simple case, consider $E$ as the initial event of ABC Corporation creating a new product. The prerequisites are $p_1=\text{sufficient capital}$ and $p_2=\text{sufficient employees}$ and both are required, so the complete contextual construct for $E$ is

$C=\left(p_1\wedge p_2\right)$

and the foregoing definitions give

$\begin{array}{c}\text{Poss}\left(E\right)=v\left(C\right)\\ =\text{min}\left[v\left(p_1\right),v\left(p_2\right)\right]\\ =\text{min}\left[\text{Prob}\left(p_1\right),\text{Prob}\left(p_2\right)\right]\end{array}$

Thus one obtains the same result as described in the intuitive rationale (1).

Next consider the slightly more complex event in (2) and (3). Let $c=\text{environmental\_issue}$ . Then the complete contextual construct becomes

$C=\left(p_1\wedge p_2\wedge \neg c\right)$

which evaluates as

$\begin{array}{c}\text{Poss}\left(E\right)=v\left(C\right)\\ =\text{min}\left[v\left(p_1\right),v\left(p_2\right),v\left(\neg c\right)\right]\\ =\text{min}\left[\text{Prob}\left(p_1\right),\text{Prob}\left(p_2\right),\text{Prob}\left(\neg c\right)\right]\\ =\text{min}\left[\text{Prob}\left(p_1\right),\text{Prob}\left(p_2\right),1-\text{Prob}\left(c\right)\right]\end{array}$

As a further example, consider the final, more complex case illustrated in (4) and (5). Again, call the event $E$ . Here let $p_1$ and $p_2$ be as above, let $c_1=\text{environmental\_issue}$ , let $c_2=\text{Jack\_unavailable}$ , and let $p_3=\text{Jill}$ . Then a complete contextual construct for $E$ is

$C=p_1\wedge p_2\wedge \neg c_1\wedge \left(\neg c_2\vee p_3\right)$ (6)

which evaluates as

$\begin{array}{c}\text{Poss}\left(E\right)=v\left(C\right)\\ =\text{min}\left[v\left(p_1\right),v\left(p_2\right),v\left(\neg c_1\right),\max \left[v\left(\neg c_2\right),v\left(p_3\right)\right]\right]\\ =\text{min}\left[\text{Prob}\left(p_1\right),\text{Prob}\left(p_2\right),\text{Prob}\left(\neg c_1\right),\text{max}\left[\text{Prob}\left(\neg c_2\right),\text{Prob}\left(p_3\right)\right]\right]\\ =\text{min}[\text{Prob}\left(p_1\right),\text{Prob}\left(p_2\right),1-\text{Prob}\left(c_1\right),\\ \text{max}\left[1-\text{Prob}\left(c_2\right),\text{Prob}\left(p_3\right)\right]]\end{array}$

Note that there can be more than one complete contextual construct depending on the manner in which these are built up from atomic constructs. For example,

$C^{\prime }=\left(p_3\vee \neg c_2\right)\wedge \neg c_1\wedge p_2\wedge p_1$ (7)

can also serve as a complete contextual construct for the given event.

5. Formalization Continued

Let us henceforth refer to a complete contextual construct for an event simply as a context for the event. Note that a context for an event is taken to include not only the prerequisites and constraints for the event, but also the manner in which these are viewed as being interrelated. Given that there can be more than one complete context for the same event, the question arises whether all such contexts will evaluate to the same possibility degree.

It might be reasonable to expect that such contexts should be logically equivalent when thus regarded as propositions of the classical propositional calculus (PC). It happens, however, that this in itself is not sufficient to guarantee that they will evaluate to the same possibility degree. The reason is that it is not generally true that, if two propositions of PC are equivalent with respect to that logic, they will also be equivalent when interpreted in the multivalent logic. This was pointed out to me in some exchanges on the Berkeley Initiative on Soft Computing (BISC) email list with Vladik Kreinovich and Dana Scott in reference to the logic of fuzzy sets, which happens to be identical to the multivalent logic considered here. Kreinovich notes that the propositions $p\vee \neg p$ and $q\vee \neg q$ are equivalent in classical logic because they are both tautologies, but if $p$ and $q$ are assigned different multivalent truth values then the two propositions typically will evaluate differently, e.g., setting $v\left(p\right)=0.4$ and $v\left(q\right)=0.8$ give $v\left(p\vee \neg p\right)=0.6$ and $v\left(q\vee \neg q\right)=0.8$ . Scott’s example consists of the propositions $\left(p\vee \neg p\right)\wedge q$ and $\left(p\wedge \neg p\right)\vee q$ , which are equivalent in classical logic but evaluate to 0 and 0.5 respectively in the multivalent logic if one sets $v\left(p\right)=0.5$ and $v\left(q\right)=0$ . This accordingly raises the question of what additional conditions on the constructs might ensure that they evaluate to the same possibility degree. The following proposes an answer.

To begin, let us review some well-known facts regarding PC. The language of PC uses propositional variables $p_1,p_2,\cdots$ , some connectives denoted $\wedge$ , $\vee$ , and $\neg$ , and parentheses (and). The propositions are defined by:

1) propositional variables are propositions,

2) if $p$ and $q$ are propositions, then so are $\left(\neg p\right)$ , $\left(p\wedge q\right)$ , and $\left(p\vee q\right)$ ,

3) nothing is a proposition except as required by items 1 and 2.

The three given connectives are adequate for the language of PC, since the connectives $\to$ and $\leftrightarrow$ can be defined in terms of these by taking $\left(p\to q\right)$ as an abbreviation for $\left(\neg p\vee q\right)$ and taking $\left(p\leftrightarrow q\right)$ as an abbreviation for $\left(\left(p\to q\right)\wedge \left(q\to p\right)\right)$ (see [18] or [19]). It is assumed that the reader is familiar with the basics of PC. Parentheses will be dropped when the intended grouping is clear; in particular, outermost parentheses are always dropped; negation, $\neg$ , takes priority over both conjunction, $\wedge$ , and disjunction, $\vee$ ; associativity is assumed to be to the right.

Taking 1 and 0 to stand for the truth values T and F, the classical semantics for this language can be defined in terms of a valuation mapping $v:\text{propositions}\to \left\{1,0\right\}$ according to:

1) if $p$ is propositional variable, then $v\left(p\right)\in \left\{1,0\right\}$ ,

2) if $p$ is of the form $\neg q$ , where $q$ is a proposition, then $v\left(p\right)=1-v\left(q\right)$ ,

3) if $p$ is of the form $q\wedge r$ , where $q$ and $r$ are propositions, then $v\left(p\right)=\min \left(v\left(q\right),v\left(r\right)\right)$ ,

4) if $p$ is of the form $q\vee r$ , where $q$ and $r$ are propositions, then $v\left(p\right)=\max \left(v\left(q\right),v\left(r\right)\right)$ .

The semantics for possibilistic logic can be obtained from this by taking the unit interval $\left[0,1\right]$ in place of the set $\left\{1,0\right\}$ . In this case, the members of $\left[0,1\right]$ are interpreted as possibility degrees in essentially the same sense as this term was used in the foregoing. Two propositions $p$ and $q$ are equivalent with respect to either semantics if one has $v\left(p\right)=v\left(q\right)$ for all choices for the respective versions of $v$ , i.e., all mappings into $\left\{1,0\right\}$ for classical logic, and all mappings into $\left[0,1\right]$ for possibilistic logic.

A literal is a proposition of the form $p$ or $\neg p$ , where $p$ is a propositional variable. A disjunctive normal form (DNF) is typically defined by saying that it is a disjunction of one or more conjunctions, each of which is a conjunction of one or more literals (see [18], p. 23), or more exactly, that it is a proposition of the form ${\vee }_{i=1}^m\left({\wedge }_{j=1}^n{Q}_{i,j}\right)$ , where each $Q_{i,j}$ is a literal (see [19], p. 17).³ It should be noted, however, that such an expression strictly speaking does not qualify as a proposition of PC unless one assumes association to the left or right. For example, where $p_1,p_2,p_3$ are propositions, the expressions $\left(\left(p_1\wedge p_2\right)\wedge p_3\right))$ and $\left(p_1\wedge \left(p_2\wedge p_3\right)\right)$ are propositions, but the expression $\left(p_1\wedge p_2\wedge p_3\right)$ is not. Accordingly, the typical definition is in this respect ambiguous. More exactly, what is wanted is that a proposition is a DNF if it is of the form ${\vee }_{i=1}^m\left({\wedge }_{j=1}^n{Q}_{i,j}\right)$ , where each $Q_{i,j}$ is a literal, and, in addition, either this expression employs associativity to the right, or it can be converted into an expression that employs associativity to the right by applying the rules of associativity, namely, for arbitrary propositions $p,q,r$ ,

replace $\left(p\vee q\right)\vee r)$ with $\left(p\vee \left(q\vee r\right)\right)$ ,

replace $\left(p\vee \left(q\vee r\right)\right)$ with $\left(\left(p\vee q\right)\vee r\right)$ ,

replace $\left(p\wedge q\right)\wedge r)$ with $\left(p\wedge \left(q\wedge r\right)\right)$ ,

replace $\left(p\wedge \left(q\wedge r\right)\right)$ with $\left(\left(p\wedge q\right)\wedge r\right)$ .

These rules are justified by the fact that they amount to replacing a proposition with one that is logically equivalent. Following [19], p. 16, the conjunctions in a DNF will be referred to as basic conjunctions.

It is well-known that every proposition of PC has an equivalent DNF. Semantic arguments proving this may be found in both of the cited references. There also is a well-known algorithm for converting a proposition into a DNF; see the page at [20], which, in turn, references [21]. This algorithm may be given in the form of a recursive procedure conv as follows. For an arbitrary proposition $\pi$ of PC,

1) If $\pi$ is a literal, stop.

2) If $\pi$ is of the form $\neg \neg p$ , replace $\pi$ with $\text{conv}\left(p\right)$ .

3) If $\pi$ is of the form $\neg \left(p\vee q\right)$ replace $\pi$ with $\text{conv}\left(\neg p\right)\wedge \text{conv}\left(\neg q\right)$ .

4) If $\pi$ is of the form $\neg \left(p\wedge q\right)$ , replace $\pi$ with $\text{conv}\left(\neg p\right)\vee \text{conv}\left(\neg q\right)$ .

5) If $\pi$ is of the form $p\vee \left(q\wedge r\right)$ , replace $\pi$ with $\left(\text{conv}\left(p\right)\vee \text{conv}\left(q\right)\right)\wedge \left(\text{conv}\left(p\right)\vee \text{conv}\left(r\right)\right)$ .

6) If $\pi$ is of the form $p\wedge \left(q\vee r\right)$ , replace $\pi$ with $\left(\text{conv}\left(p\right)\wedge \text{conv}\left(q\right)\right)\vee \left(\text{conv}\left(p\right)\wedge \text{conv}\left(r\right)\right)$ .

7) If $\pi$ is of the form $\left(p\wedge q\right)\vee r$ , replace $\pi$ with $\left(\text{conv}\left(p\right)\vee \text{conv}\left(r\right)\right)\wedge \left(\text{conv}\left(q\right)\vee \text{conv}\left(r\right)\right)$ .

8) If $\pi$ is of the form $\left(p\vee q\right)\wedge r$ , replace $\pi$ with $\left(\text{conv}\left(p\right)\wedge \text{conv}\left(r\right)\right)\vee \left(\text{conv}\left(q\right)\wedge \text{conv}\left(r\right)\right)$ .

Item 2 applies the Idempotence Law, items 3 and 4 apply De Morgan’s Laws, and items 5 and 6 apply the Distributive Laws. The fact that this conversion process produces an equivalent proposition is established by the fact that these laws are all valid in PC. It is also known that PC validates the Commutative and Associative Laws.

Let us say that two propositions $p$ and $q$ of PC are strongly equivalent if $\text{conv}\left(p\right)$ and $\text{conv}\left(q\right)$ can be converted into one another using only the Commutative and Associative Laws. In effect, this says that, not only are $p$ and $q$ logically equivalent, but their DNFs differ from one another essentially only in the order of their basic conjunctions and the order of the literals within the basic conjunctions. Similarly let us say that two contextual constructs $C$ and $C^{\prime }$ , are strongly equivalent if they are strongly equivalent when considered as propositions of PC.

Next let us note the following facts about the multivalent logic. First, the Distributive Laws hold. Consider

$p\vee \left(q\wedge r\right)$ and $\left(p\vee q\right)\wedge \left(p\vee r\right)$

By examining the six possible arrangements of $p$ , $q$ , and $r$ with respect to their numerical values (i.e., $v\left(p\right)\le v\left(q\right)\le v\left(r\right)$ , $v\left(p\right)\le v\left(r\right)\le v\left(q\right)$ , $v\left(q\right)\le v\left(p\right)\le v\left(r\right)$ , $v\left(q\right)\le v\left(r\right)\le v\left(p\right)$ , $v\left(r\right)\le v\left(p\right)\le v\left(q\right)$ , and $v\left(r\right)\le v\left(q\right)\le v\left(p\right)$ ) one can see that in all cases both of the above formulas evaluate to the same number. Similarly for

$p\wedge \left(q\vee r\right)$ and $\left(p\wedge q\right)\vee \left(p\wedge r\right)$

Second, the Commutative Law holds. To wit, for all propositions $p,q$ with possibility degrees $v\left(p\right),v\left(q\right)$ , we have

$\begin{array}{c}v\left(p\wedge q\right)=\min \left(v\left(p\right),v\left(q\right)\right)\\ =\min \left(v\left(q\right),v\left(p\right)\right)\\ =v\left(q\wedge p\right)\end{array}$

Last, the Associative Laws hold. For all propositions $p,q,r$ with possibility degrees $v\left(p\right),v\left(q,v\left(r\right)\right)$ , we have

$\begin{array}{c}v\left(\left(p\wedge q\right)\wedge r\right)=\min \left(\min \left(v\left(p\right),v\left(q\right)\right),v\left(r\right)\right)\\ =\min \left(v\left(p\right),\min \left(v\left(q\right),v\left(r\right)\right)\right)\\ =v\left(p\wedge \left(q\wedge r\right)\right)\end{array}$

and similarly for $\vee$ with max.

We are now in a position to establish the following result.

Theorem. If two contextual constructs $C$ and $C^{\prime }$ are strongly equivalent, then $v\left(C\right)=v\left(C^{\prime }\right)$ .⁴

Proof. Let $C$ and $C^{\prime }$ be two strongly equivalent contextual constructs. Consider the DNFs $\text{conv}\left(C\right)$ and $\text{conv}\left(C^{\prime }\right)$ . Note that, because of the rules for building contextual constructs, none of items 2, 3, or 4 in the foregoing algorithm conv will need to be applied, since the types of propositions to which they are applied are not conceptual constructs. Thus, only items 5, and 6 will be employed by the conversion process, and these apply only the Distributive Laws, which we have just seen are valid in the multivalent logic. Thus $v\left(\text{conv}\left(C\right)\right)=v\left(C\right))$ and $v\left(\text{conv}\left(C^{\prime }\right)\right)=v\left(C^{\prime }\right)$ .

By the definition of strongly equivalent for contextual constructs, each of $\text{conv}\left(C\right)$ and $\text{conv}\left(C^{\prime }\right)$ can be converted into the other using only the Commutative and Associative Laws. Since, as shown in the foregoing, these laws are also valid in possibilistic logic, it follows that $v\left(\text{conv}\left(C\right)\right)=v\left(\text{conv}\left(C^{\prime }\right)\right)$ . This together with the foregoing gives the desired result:

$v\left(C\right)=v\left(\text{conv}\left(C\right)\right)=v\left(\text{conv}\left(C^{\prime }\right)\right)=v\left(C^{\prime }\right)$

◼

This theorem thus establishes the desired condition for equivalence between contexts for any given event. To illustrate, we can see that the foregoing constructs (6) and (7) are strongly equivalent, and therefore evaluate to the same possibility value. First, let us write these propositions with the parentheses implied by assuming associativity to the right (but omitting outermost parentheses),

$C=p_1\wedge \left(p_2\wedge \left(\neg c_1\wedge \left(\neg c_2\vee p_3\right)\right)\right)$

$C^{\prime }=\left(p_3\vee \neg c_2\right)\wedge \left(\neg c_1\wedge \left(p_2\wedge p_1\right)\right)$

These have the property that $\text{conv}\left(C\right)$ and $\text{conv}\left(C^{\prime }\right)$ can be converted into one another by using only the Commutative and Associative Laws. Following is an application of conv to $C$ :

$p_1\wedge \left(p_2\wedge \left(\left(\neg c_1\wedge \neg c_2\right)\vee \left(\neg c_1\wedge p_3\right)\right)\right)$ , using conv item (6)

$p_1\wedge \left(\left(p_2\wedge \left(\neg c_1\wedge \neg c_2\right)\right)\vee \left(p_2\wedge \left(\neg c_1\wedge p_3\right)\right)\right)$ , using conv item (6)

$\left(p_1\wedge \left(p_2\wedge \left(\neg c_1\wedge \neg c_2\right)\right)\right)\vee \left(p_1\wedge \left(p_2\wedge \left(\neg c_1\wedge p_3\right)\right)\right)$ , using conv item (6) (8)

Next is an application of conv to $C^{\prime }$ :

$\left(p_3\wedge \left(\neg c_1\wedge \left(p_2\wedge p_1\right)\right)\right)\vee \left(\neg c_2\wedge \left(\neg c_1\wedge \left(p_2\wedge p_1\right)\right)\right)$ , using conv item (8) (9)

It is easy to see that (8) and (9) satisfy the conversion requirement.

6. Complex Events

The foregoing has defined a notion of possibility for an event whose occurrence is predicated on a set of prerequisites and/or constraints. This in turn gives rise to the issue of an event whose possibility is predicated on the possibilities of some precursor events. More exactly, we here consider an event $E$ whose possibility depends on the possibility of some Boolean combination $E^{\prime }$ of precursor events $E_1,\cdots ,E_n$ , where it is assumed that possibility values for $E_1,\cdots ,E_n$ are known. The former type of event, $E$ , may be referred to as a simple event and the latter, $E^{\prime }$ , as a complex event. At issue is how to compute $\text{Poss}\left(E\right)$ given $\text{Poss}\left(E_1\right),\cdots ,\text{Poss}\left(E_n\right)$ .

It is natural to compute the possibility of the Boolean combination $E^{\prime }$ in terms of the possibilities of $E_1,\cdots ,E_n$ using the standard possibility theory interpretations of $\wedge$ , $\vee$ , and $\neg$ as the operations min, max, and $1-$ as discussed in the foregoing. The question, then, is how to determine the possibility of $E$ given the possibility of the Boolean combination $E^{\prime }$ .

For this it is important to note that the connection between $E$ and $E^{\prime }$ is a logical relationship. This may be contrasted with probability theory where the conditional probability of $E$ given $E^{\prime }$ may be interpreted as a causality relation. In possibility theory there is no role for the notion of causation. The possibility relation between $E$ and $E^{\prime }$ is simply that, if $E^{\prime }$ is possible, then so is $E$ ; i.e., it is a purely logical inference.

Because of this it is natural to compute the possibility of $E$ in terms of the possibility of $E^{\prime }$ by means of some possibilistic version of the classical rule of Modus Ponens. This amounts to selecting a suitable inference operator, i.e., a functional representation of the logical $\to$ . In the present context it is reasonable to assume that the inference $E^{\prime }\to E$ is true, in which case its truth value in a multivalent logic would be 1. Given this, then a value for $\text{Poss}\left(E\right)$ can be computed from the value for $\text{Poss}\left(E^{\prime }\right)$ according to the function specified for $\to$ .

To illustrate, consider the Łukasiewicz $\to$ operator from the aforementioned ${\text{Ł }}_{{\aleph }_1}$ , cf. [11], p. 337, defined by

$v\left(E^{\prime }\to E\right)=\min \left(1,1-v\left(E^{\prime }\right)+v\left(E\right)\right)$

where the valuation function $v$ assumes values in the unit interval $\left[0,1\right]$ . In the present treatment, the values $v\left(E^{\prime }\right)$ and $v\left(E\right)$ are taken as being the possibility values $\text{Poss}\left(E^{\prime }\right)$ and $\text{Poss}\left(E\right)$ . Thus, if we are given that $v\left(E^{\prime }\to E\right)=1$ and a numerical value for $\text{Poss}\left(E^{\prime }\right)$ , the value for $\text{Poss}\left(E\right)$ can be determined as follows.

From the foregoing definition of the Łukasiewicz $\to$ using the min operation, we have $1-\text{Poss}\left(E^{\prime }\right)+\text{Poss}\left(E\right)\ge 1$ . This implies that $\text{Poss}\left(E\right)\ge \text{Poss}\left(E^{\prime }\right)$ . Thus one obtains a range of values for $\text{Poss}\left(E\right)$ . Under the current circumstances, however, there is no loss in simply assuming that $\text{Poss}\left(E\right)=\text{Poss}\left(E^{\prime }\right)$ . This then provides an effective way of applying Modus Ponens to chains of inferences of the form $E^{\prime }\to E$ .

But this is only one of many available choices for an inference operator. Numerous other such operators have been discussed throughout the literature. In particular nine different versions of Modus Pones are discussed in [2] (pp. 130-131) and ten are discussed in [23]. Which one to employ depends on the preferences of the user and the needs of the application.

Note that, with the Ł ukasiewicz operator under the foregoing assumptions, the degree of possibility propagates unchanged through chains of inferences. With other versions of logical inference these degrees may degrade as the chain grows longer. In some cases, the possibility value can degrade rather quickly toward 0.5, indicating complete uncertainty. This may be suitable for modelling some situations, and not for others.

7. An Example: Vehicle Waypoint Navigation

These ideas may be illustrated with a hypothetical real-world application. As mentioned, possibility theory may profitably be applied to problems of planning. A plan consists of a sequence of events leading from a start state to a goal state. Possibility theory can play a role when there is more than one plan for the same start-goal mission. The theory can be applied to compute a degree of possibility for each plan, from which one can choose the plan that has the highest possibility degree and thus may be regarded as the easiest to complete.

Applying the theory requires that, for each event, one assigns suitable prerequisites and constraints, and then for each of these prerequisites and constraints finds data sources that can be used to estimate their probabilities. However, if desired, or in case relevant data is not available, such probabilities can be assigned subjectively. Given that this has been accomplished, the degrees of possibility for the various plans can be computed in the manner that is illustrated in this example.

Figure 1. Example street network.

Consider the task of navigating a vehicle (with or without a driver) through a network of city streets. Suppose that, as depicted in Figure 1, it is desired to travel from point A to point H, and some mapping service has identified several alternative routes, also shown in Figure 1. Each node in the graph is a waypoint and each link between two waypoints is a leg. In this case each route comprises a plan, where the tasks consist of navigating the legs of the route, i.e., each leg comprises a task. As can be seen in Figure 1, there are three plans, route A, B, D, G, H, route A, B, E, G, H, and route A, C, F, G, H.

Further suppose that this is taking place in a “smart city”, which provides the vehicle with real-time information concerning traffic conditions on all the indicated legs of the journey. The objective is to determine the degree of possibility that the vehicle can reach waypoint H at a speed of at least the designated speed limits for the various legs.

For the purposes of this example, assume also that the vehicle reassesses this possibility at each waypoint where it must make a decision regarding which way to proceed. Thus, at point A the vehicle may decide to proceed to either B or C. If it chooses B, then, after arriving at B, it must choose between D and E and then proceed to G and H. If it chooses C, then it is committed to the path A, C, F, G, H.

For simplicity, let us assume that the prerequisites and constraints are the same for all legs. In a more realistic example, of course, this would not be the case. Let the prerequisites for all legs be $p_1$ = “the vehicle is in proper operating condition” and $p_2$ = “the driver (human or robot) is competent”. Constraints that may apply to each leg are possible causes of traffic congestion that impede the vehicle’s progress. These may include $c_1$ = “high traffic volume (rush hours)”, $c_2$ = “bad weather (rain, snow, ice)”, $c_3$ = “traffic accidents”, and $c_4$ = “road construction”.

One might reasonably set the probability of $p_1$ to be strictly less than 1 to account for the possibility that the vehicle might suffer mechanical problems (flat tire, engine trouble). Similarly, one might set the probability of $p_2$ to be less than 1 to account for the possibility that the driver might be in training, or impaired (alcohol, drugs), sleepy, or experience health issues. Also, given an adequate monitoring system, these values could change during the course of the journey. Constraints also may vary throughout the trip, e.g., a traffic accident can suddenly occur, or the daily rush hour can come into effect, or the weather can change. While some of these probabilities may be assigned subjectively, others might be based on statistical samplings. For example, data regarding traffic congestion during different times of the day could be used to determine the degree to which this can become a constraint. Similar remarks may apply to the frequency of traffic accidents on a particular leg of the vehicle’s journey. In addition, weather forecasts could be invoked to determine the likelihood of adverse conditions on later legs of the journey.

For the sake of this example, assume that a complete contextual construct for each leg is $C=p_1\wedge p_2\wedge \neg c_1\wedge \neg c_2\wedge \neg c_3\wedge \neg c_4$ . To identify these items for each leg $i=1,\cdots ,9$ shown in Figure 1, add the subscript $i$ , i.e., write $C_i=p_{1,i}\wedge p_{2,i}\wedge \neg c_{1,i}\wedge \neg c_{2,i}\wedge \neg c_{3,i}\wedge \neg c_{4,i}$ . Then, in accordance with the foregoing theory, for each $i$ , if $E_i$ is the event of the car traveling leg $i$ at the designated speed limit, it follows that

$\begin{array}{c}\text{Poss}\left(E_i\right)=v\left(C_i\right)\\ =\min (\text{Prob}\left(p_{1,i}\right),\text{Prob}\left(p_{2,i}\right),1-\text{Prob}\left(c_{1,i}\right),\\ 1-\text{Prob}\left(c_{2,i}\right),1-\text{Prob}\left(c_{3,i}\right),1-\text{Prob}\left(c_{4,i}\right))\end{array}$

The indicated probabilities may be provided by subjective or objective analysis, where by “objective” is here meant “based on statistical sampling”. For example, consider constraint $c_1$ . Traffic volume may be taken as a linguistic variable with possible values high, medium, low, where volume is measured as the number of vehicles passing a given point per minute. For each hour of the day, the probability that the traffic will be high during that time can be determined by historical statistical samplings; e.g., the probability that congestion will be high around 5:30 PM on a Monday might be 0.9. Other probabilities may depend on subjective evaluations or current reports. For example, the probability of a traffic accident (constraint $c_3$ ) on a given leg based on statistical samplings might be generally low, say 0.1, but if the smart city system announces that there is an accident on some leg, then the evaluation immediately jumps to 1.0. In this manner, one can determine $\text{Poss}\left(E_i\right)$ for each leg $i$ for any time.

Accordingly, the value $\text{Poss}\left(E_i\right)$ can be computed dynamically while the vehicle is travelling for any time of day and any day of the week. Given this ability, the procedure for the vehicle’s decisions regarding which path to take goes as follows.

While at waypoint A, the choice is whether to proceed to B or C. Let $E_B$ be the event of traveling from A to H through waypoint B, and let $E_C$ be the event of traveling through C. Then these are the composite events

$E_B=E_1\wedge \left(\left(E_3\wedge E_6\right)\vee \left(E_4\wedge E_7\right)\right)\wedge E_9$

$E_C=E_2\wedge E_5\wedge E_8\wedge E_9$ , and

in accordance with the foregoing we can compute

$\begin{array}{l}\text{Poss}\left(E_B\right)=\min (\text{Poss}\left(E_1\right),\max (\min \left(\text{Poss}\left(E_3\right),\text{Poss}\left(E_6\right)\right),\\ \min \left(\text{Poss}\left(E_4\right),\text{Poss}\left(E_7\right)\right),\text{Poss}\left(E_9\right)))\end{array}$

$\text{Poss}\left(E_C\right)=\min \left(\text{Poss}\left(E_2\right),\text{Poss}\left(E_5\right),\text{Poss}\left(E_8\right),\text{Poss}\left(E_9\right)\right)$ ,

and choose the path with the higher value. If the path through waypoint B is chosen, then upon reaching that waypoint, consider $E_D=E_3\wedge E_6\wedge E_9$ and $E_E=E_4\wedge E_7\wedge E_9$ , and compute

$\text{Poss}\left(E_D\right)=\min \left(\text{Poss}\left(E_3\right),\text{Poss}\left(E_6\right),\text{Poss}\left(E_9\right)\right)$ , and

$\text{Poss}\left(E_E\right)=\min \left(\text{Poss}\left(E_4\right),\text{Poss}\left(E_7\right),\text{Poss}\left(E_9\right)\right)$

and choose the path through D or E depending on which of these is higher. In this manner one finds the path from A to H that is most possible to traverse at a speed that is at least as high as the designated speed limit.

As a point of terminology, one might refer to the process of traversing a leg of the journey as an activity and the completion of this process as an event indicated by the waypoint at the end of the leg. In this case, the prerequisites and constraints apply to the activity, and the computed possibility measure represents the possibility of successfully completing this activity as well as the possibility of the actual occurrence of the event.

8. Comparison with Probability Theory

Probability theory also provides a semantics for the logical $\neg$ , $\wedge$ , and $\vee$ . The following borrows definitions and theorems from the textbook [24].

The theory of probability is based on the concept of a sample space $S$ consisting of a set of outcomes $o$ from an experiment, like the tossing of one or more coins or the rolling of one or more six-sided dice. An event $E$ is a subset of $S$ . The event is said to occur as the result of an experiment if the outcome $o$ is a member of $E$ .

Each outcome $o$ in $S$ is assumed to have been assigned a value, $\text{Prob}\left(o\right)$ , representing that outcome’s probability of occurrence, with the properties (i) $\text{Prob}\left(o\right)\ge 0$ , for all $o$ in $S$ , and (ii) the sum of the values $\text{Prob}\left(o\right)$ over all the $o$ in $S$ equals 1. Then, the probability $\text{Prob}\left(E\right)$ of an event $E$ is computed as the sum of the probabilities of the outcomes in $E$ .

Based on these definitions, it can be proven that, where $\cup$ , $\cap$ , and $c$ represent ordinary set union, intersection, and complement, and $E$ and $F$ are any events,

$\text{Prob}\left(E\cup F\right)=\text{Prob}\left(E\right)+\text{Prob}\left(F\right)-\text{Prob}\left(E\cap F\right)$

and

$\text{Prob}\left(E^c\right)=1-\text{Prob}\left(E\right)$ .

Two events $E$ and $F$ are said to be independent if

$\text{Prob}\left(E\cap F\right)=\text{Prob}\left(E\right)\times \text{Prob}\left(F\right)$ .

An event $E$ can be associated with a logical proposition $p$ by taking $p$ as expressing “$E$ has occurred” and taking the truth value $v\left(p\right)$ as the probability value $\text{Prob}\left(E\right)$ . Then, by virtue of the above, a logic may be defined for propositions representing independent events by setting

$v\left(\neg p\right)=1-v\left(p\right)$

$v\left(p\wedge q\right)=v\left(p\right)\times v\left(q\right)$

$v\left(p\vee q\right)=v\left(p\right)+v\left(q\right)-v\left(p\wedge q\right)$

These definitions of the logical connectives might be considered for use in place of the multivalent interpretations throughout the foregoing discussion, ultimately, or ostensibly, providing a measure of the likelihood of successfully completing the journey along each of the possible paths, after which one could choose whichever plan is most likely to succeed. However, this probabilistic interpretation, in most applications, would produce unrealistic results. This may be illustrated in terms of the foregoing waypoint navigation example. For an event (leg traversal) $E_i$ , the probability of this event would be computed as the product of the probabilities of the prerequisites and the opposites of the constraints. Given that these would all be real numbers less than 1, this product would typically be very low, possibly close to 0. Accordingly, this would imply that it is actually very unlikely that the leg traversal would occur. This, however, does not square with common sense, and it therefore suggests that probability theory doesn’t provide a realistic model of this kind or real-world situation.

Last, it may be conjectured that the version of possibility presented in this paper provides a more intuitively compelling model of natural human reasoning than does probability theory for these kinds of applications. The type of reasoning and decision making as illustrated in the case of Jane in Section 2 seems wholly natural and may well be a correct model of this kind of reasoning, i.e., using min and max for the logical and and or. Of course, it would require suitable Cognitive Science experiments to verify that this is true. But, in any case, it seems clear that humans do not take the trouble of computing the relevant probabilities for such logical combinations. Day-to day human reasoning and decision making is much more fluid and intuitive and surely does not entail such complex cogitations.

9. Prospects for Applications

Probability theory is concerned with prediction. In this context, one wants to know, given certain conditions, what is the likelihood that a given event will occur. In contrast, possibility theory has no concern with prediction. Rather this addresses the situation where one wants to know, given certain preconditions, what is the possibility that a given event may occur. Following the suggestion by Zadeh in [1], as discussed in the foregoing Section 2, the possibility value of an event may be interpreted as a measure of the ease with which that event may occur. In an application such as the foregoing waypoint navigation example, an elementary event would the traversal of a leg of the journey. Accordingly, the overall possibility measure of a path through the network from the start node, A, to the goal node, H, can be taken as representing the ease with which that path may be traversed, and the objective of the analysis is to determine which path is easiest. Possibility values might also be taken as representing the feasibility of completing a task or the overall mission.

These concepts can be applied generally to any planning application. The following suggests four further potential application domains.

Robotics. Robot planning involves finding a sequence of elementary actions that will take the robot from some start state to some goal state. A well-known textbook on this subject is [25].

A variety of methods for creating and executing plans have evolved. The earliest one, STRIPS, cf. [26] (also cf. [27] [28], describes the elementary actions that the robot may perform as logical if-then rules of the form “if certain prerequisites are satisfied, then such-and-such action will be taken”, and the system uses an automated reasoning technique that attempts to prove that, given these rules, the goal can be achieved. If a proof is found, then the steps of the proof comprise a viable plan.

The success of STRIPS led to the creation of the Planning Domain Definition Language (PDDL) by M. Ghallab and others [29]. This provides a language for encoding the relevant domain knowledge and inference rules. A recent treatment of this is the book by Patrik Haslum and others [30].

This planning methodology lends itself to application of the ideas being presented here in those situations where the prerequisites of the robot actions are satisfied with some degree of probability. PDDL specifications also normally include some constraints, e.g., time of plan completion, which might also be represented in this theory. This possibilistic information would be most relevant when there is more than one viable plan for reaching the goal, in which case one can select the plan that is most possible, i.e., easiest to complete.

STRIPS/PDDL continues to be popular and has been employed in numerous robot competitions. Other planning methodologies include hierarchical task networks, cf. [31] [32]; behavior trees, cf. [33] [34], and synthesis methods, cf. [35]. These may also be amenable to some version of this theory.

Organizational Project Planning. The Critical Path Method (CPM) and the Program Evaluation and Review Technique (PERT), cf. [36]-[39], are project planning tools that are widely used throughout business, industry, and the US military. CPM works with a graphical representation of the tasks that are required to complete a project, where some tasks must precede or follow other tasks, and some tasks may run in parallel with other tasks. The graph thus comprises a network showing all the tasks that must be performed to reach from the start of the project to the end. There are typically many paths through the network from the start to the end. The critical path is the one that takes the longest time, thereby determining the minimum time required to completion. PERT augments CPM by providing additional aspects for working with times, accommodating the fact that some tasks may complete early, and some may run late, accordingly dynamically adjusting the estimate of overall time while the work is in progress.

If some or all of the tasks can be viewed as having prerequisites and/or constraints affecting the task completion, this would enable application of the current theory to determine which paths through the network are more feasible than others. This could be useful additional information about the project plan inasmuch as the shortest-time path might not be the most feasible. There would thus be a trade-off between time expectations and feasibility.

Computer Networks. Computer networks behave somewhat like the waypoint navigation problem described in Section 7. Similarly with routing a vehicle from one place to another, computer networks send packets of information from one place to another. Computer networks are much more complex than vehicular traffic systems, however. The links between nodes can be of many different types, including both hard-wired—twisted copper, co-axial cable, ethernet—and wireless—Wi-Fi, radio frequency, microwave—where Wi-Fi can be 3G, 4G, 5G, etc., and where the latter has the issue that it only works over short distances.

The present theory of possibility may be useful to provide further information about such networks. For any link in the network, the prerequisites might be very simple: only that the connection exists. There can, however, be numerous potential constraints. These include congestion due to high traffic (as with vehicles on roadways), bandwidth constraints, noise, weather (electrical storms), etc. The research in this area is primarily concerned with the efficiency and reliability of transmission. This might be augmented with a measure of the feasibility of transmission.

Computer Games. The master’s thesis by Braedon Warnick, cf. [40] showed how this notion of possibility can be used to model the decision processes of non-player characters in a simple computer game. A summary of this work had been published as [41]. Warnick agreed that this conforms to natural human decision processes, thereby providing the simulated actors with a more human-like behavior.

10. Conclusions

This paper has proposed a simple but intuitively plausible procedure for computing the degree of possibility of an event insofar as the event may be viewed as having prerequisites that enable its occurrence and/or constraints that impede its occurrence. The plausibility rests on the observation that the notion of possibility for this kind of an event is context dependent, where the context consists of those prerequisites and/or constraints. The prerequisites may be satisfied, and the constraints may manifest, with specific numerical degrees of probability. Thus, it seems reasonable to compute the possibility of the event in terms of these probabilities.

This has the advantage that one can use the computational methods of statistical sampling to determine the indicated probabilities, and then use these probabilities to determine the event’s possibility. Thus, the overall method can be objective and computational. This augments the currently existing subjective approaches and may serve as the foundation for future applications of possibility theory in practical real-world settings.

Possibility theory can play an essential role in planning applications inasmuch as it provides a tool for evaluating the feasibility of alternative plans. This opens potential opportunities to employ possibility theory in areas such as robot mission planning, organizational planning, computer networks, and computer games.

Acknowledgements

Lotfi A. Zadeh was the external examiner on my doctoral dissertation. He was my advisor’s advisor. When I entered the Systems Science PhD Program at Portland State University in 1975, I met George L. Lendaris, who had been a student of Lotfi at Berkeley. George saw that I had completed a master’s thesis in mathematical logic and showed me some of Lotfi’s papers. I immediately became interested in the prospect of formalizing human reasoning with imprecise information, and this ultimately became the topic of my doctoral research. George connected me with Lotfi, and I went to Berkeley once to give a talk. Lotfi helped me in many ways over the years, including with obtaining my current job at Florida State University and with funding for my research. He was an extraordinarily brilliant, creative, and wise human being, with a kind heart and a generous soul. He should have received the Turing award, but he wasn’t interested. He said that his legacy would be his publications. Lotfi was one of the giants.

Appendix

A software package had been produced by some undergraduate students at Florida State University that can take a street network of arbitrary complexity as input and output a listing showing a most possible solution path together with a graphical visualization. The most recent student to work on this is Analia Castellanos, who extended a system that had been developed previously by a team consisting of Maia Huber, Samuel Cohen, and Julian Olivier. An example input file is shown here. This system, together with three sample input files and user instructions can be obtained at https://github.com/danielgschwartz/VehicleWaypointNavigation.

A sample input file is as follows. This uses a slightly more complex street network than in Figure 1. Here a leg of the network is referred to as a step, and each step is described by its start and end nodes, its prerequisites and constraints, and, for each prerequisite and constraint, an assumed probability of occurrence. In contrast with the example in Section 7, it is allowed that different legs may have different sets of prerequisites and constraints. This serves to illustrate the flexibility of the theory and show that the software supports this.

Number of steps: 10 Origin: A Destination: H Step 1 origin: A Step 1 destination: B Constraint(s): red light, car accident Prerequisite(s): car turns on, gas in tank Probability of “red light”: 0.2 Probability of “car accident”: 0.2 Probability of “car turns on”: 0.9 Probability of “gas in tank”: 0.8 Step 2 origin: A Step 2 destination: C Constraint(s): road closure, traffic Prerequisite(s): gas in tank Probability of “road closure”: 0.1 Probability of “traffic”: 0.1 Probability of “gas in tank”: 0.9 Step 3 origin: B Step 3 destination: D Constraint(s): traffic, car accident Prerequisite(s): gas in tank Probability of “traffic”: 0.4 Probability of “car accident”: 0.2 Probability of “gas in tank”: 0.8 Step 4 origin: B Step 4 destination: E Constraint(s): red light, detour Prerequisite(s): car turns on, gas in tank Probability of “red light”: 0.3 Probability of “detour”: 0.1 Probability of “car turns on”: 0.9 Probability of “gas in tank”: 0.8 Step 5 origin: C Step 5 destination: F Constraint(s): car accident, road closure Prerequisite(s): gas in tank Probability of “car accident”: 0.2 Probability of “road closure”: 0.3 Probability of “gas in tank”: 0.9 Step 6 origin: D Step 6 destination: G Constraint(s): traffic, construction Prerequisite(s): gas in tank Probability of “traffic”: 0.4 Probability of “construction”: 0.3 Probability of “gas in tank”: 0.8 Step 7 origin: E Step 7 destination: G Constraint(s): car accident, traffic Prerequisite(s): gas in tank Probability of “car accident”: 0.3 Probability of “traffic”: 0.4 Probability of “gas in tank”: 0.9 Step 8 origin: F Step 8 destination: G Constraint(s): detour, construction Prerequisite(s): gas in tank Probability of “detour”: 0.5 Probability of “construction”: 0.3 Probability of “gas in tank”: 0.7 Step 9 origin: G Step 9 destination: H Constraint(s): traffic, road closure Prerequisite(s): gas in tank Probability of “traffic”: 0.3 Probability of “road closure”: 0.2 Probability of “gas in tank”: 0.9 Step 10 origin: C Step 10 destination: G Constraint(s): detour, construction Prerequisite(s): gas in tank Probability of “detour”: 0.1 Probability of “construction”: 0.1 Probability of “gas in tank”: 0.9 Desired path origin: A Desired path destination: H

The output listing generated by this input file is as follows, and the resulting graphical visualization is shown in Figure A1. Here the start node is at the top and the goal node is at the bottom. The numbers on the legs are the computed possibility degrees, and the solution path having the highest possibility is shown in green.

max prereqs: 2 max constraints: 2 first segment row: ['A', 'B', 0.9, 0.8, 0.2, 0.2] Segments created: ['A', 'B', 0.9, 0.8, 0.2, 0.2] ['A', 'C', 0.9, 1.0, 0.1, 0.1] ['B', 'D', 0.8, 1.0, 0.4, 0.2] ['B', 'E', 0.9, 0.8, 0.3, 0.1] ['C', 'F', 0.9, 1.0, 0.2, 0.3] ['D', 'G', 0.8, 1.0, 0.4, 0.3] ['E', 'G', 0.9, 1.0, 0.3, 0.4] ['F', 'G', 0.7, 1.0, 0.5, 0.3] ['G', 'H', 0.9, 1.0, 0.3, 0.2] ['C', 'G', 0.9, 1.0, 0.1, 0.1] Segment A-B: Poss = 0.8 Segment A-C: Poss = 0.9 Segment B-D: Poss = 0.6 Segment B-E: Poss = 0.7 Segment C-F: Poss = 0.7 Segment D-G: Poss = 0.6 Segment E-G: Poss = 0.6 Segment F-G: Poss = 0.5 Segment G-H: Poss = 0.7 Segment C-G: Poss = 0.9 Graph adjacency list: A -> ['B', 'C'] B -> ['D', 'E'] C -> ['F', 'G'] D -> ['G'] E -> ['G'] F -> ['G'] G -> ['H'] Possibility of Path A-B-D-G-H: 0.6 Possibility of Path A-B-E-G-H: 0.6 Possibility of Path A-C-F-G-H: 0.5 Possibility of Path A-C-G-H: 0.7 Choosing Path A-C-G-H with Possibility 0.7 Possibility of Path C-F-G-H: 0.5 Possibility of Path C-G-H: 0.7 Possibility of Path G-H: 0.7 Choosing Path C-G-H with Possibility 0.7 Full chosen path: A-C-G-H Saved: final_path.png

Figure A1. Street network with solution path.

NOTES

¹An explicit definition of the semantics for the logical “implies” and “not” appears on page 72 of [13].

²This work unifies and expands material formerly published as [14] and [15]. The expansion includes a substantial revision of the introductory section and a new section discussing of the differences between possibility and probability, and it suggests some potential future application domains. It also provides new examples to illustrate the main ideas, and it corrects a few mathematical oversights in the previous publications. In addition, it adds an appendix that provides the results of a Python program that implements an example application and a link to the code.

³The previous work [14] employed conjunctive normal forms. For the present purposes, the two approaches are equivalent. The DNF approach is adopted here so that one may rely on the references cited in the following for the conversion algorithm conv.

⁴A generalization of this result that applies to the full logic of fuzzy propositions, and not just conceptual constructs, has been published as [22]. The following proof, as well as the foregoing definitions and analysis, repeats some of that material and is provided here so that the present treatment will be self-contained.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Zadeh, L.A. (1978) Fuzzy Sets as a Basis for a Theory of Possibility. Fuzzy Sets and Systems, 1, 3-28.[CrossRef]
[2]	Dubois, D. and Prade, H. (1988) Possibility Theory. Plenum Press.
[3]	Yager, R.R. (1982) Fuzzy Set and Possibility Theory: Recent Developments. Pergamon Press.
[4]	Wang, P.P. (2012) Advances in Fuzzy Sets, Possibility Theory, and Applications. Springer.
[5]	Dubois, D. and Prade, H. (2015) Possibility Theory and Its Applications: Where Do We Stand? In: Kacprzyk, J. and Pedrycz, W., Eds., Springer Handbook of Computational Intelligence, Springer, 31-60.[CrossRef]
[6]	Dubois, D. and Prade, H. (2015) Practical Methods for Constructing Possibility Distributions. International Journal of Intelligent Systems, 31, 215-239.[CrossRef]
[7]	Zadeh, L.A. (1965) Fuzzy Sets. Information and Control, 8, 338-353.[CrossRef]
[8]	Klement, E.P., Mesiar, R. and Pap, E. (2000) Triangular Norms. Springer.
[9]	Hájek, P. (2001) Metamathematics of Fuzzy Logic. Springer.
[10]	Navara, M. (2007) Triangular Norms and Conorms. Scholarpedia, 2, Article 2398.[CrossRef]
[11]	Rescher, N. (1969) Many-Valued Logic. McGraw-Hill.
[12]	Łukasiewicz, J. and Tarski, A. (1930) Untersuchungen über den aussagenkalkül [Investigations into the Sentential Calculus]. Comptes Rendus des séances de la Société des Sciences et des Lettres de Varsovie, 23, 30-50. (In German)
[13]	Łukasiewicz, J. (1930) Philosophische bemerkungen zu mehrwertigen systemen des aus-sagenkalküls [Philosophical Remarks on Many-Valued Systems of Propositional Logic]. Comptes Rendus des séances de la Société des Sciences et des Lettres de Varsovie, 23, 51-77. (In German)
[14]	Schwartz, D.G. (2016) On the Possibility of an Event. Proceedings of the 18th International Conference on Artificial Intelligence (ICAI’16), Las Vegas, 25-28 July 2016, 45-51.
[15]	Schwartz, D.G. (2017) A Theory of Event Possibility with Application to Vehicle Waypoint Navigation. In: Melin, P., Castillo, O., Kacprzyk, J., Reformat, M. and Melek, W., Eds., Fuzzy Logic in Intelligent System Design, Springer, 329-334.[CrossRef]
[16]	Kolmogorov, A.N. (2018) Foundations of the Theory of Probability. 2nd Edition, Courier Dover Publications.
[17]	Burlow, J. (2015) Severe Storms Possible Ahead of Christmas Day. Tallahassee Democrat, 3A p.
[18]	Mendelson, E. (2015) Introduction to Mathematical Logic. 6th Edition, CRC Press.
[19]	Hamilton, A.G. (1988) Logic for Mathematicians, Revised Edition. Cambridge University Press.
[20]	Wikipedia (2026) Probability Axioms. https://en.wikipedia.org/wiki/Probability_axioms
[21]	Dershowitz, N. and Jouannaud, J. (1990) Rewrite Systems. In: Van Leeuwen, J., Ed., Formal Models and Semantics, Elsevier, 243-320.[CrossRef]
[22]	Schwartz, D.G. (2024) Strong Equivalence of Fuzzy Propositions. Proceedings of the North American Fuzzy Information Processing Society (NAFIPS), South Padre Island, 27-29 May 2024.
[23]	Schwartz, D.G. (1989) Fuzzy Inference in a Formal Theory of Semantic Equivalence. Fuzzy Sets and Systems, 31, 205-216.[CrossRef]
[24]	Goldberg, S. (1986) Probability: An Introduction. Courier Corporation.
[25]	Ghallab, M., Nau, D. and Traverso, P. (2004) Automated Planning: Theory and Practice. Elsevier.
[26]	Fikes, R.E. and Nilsson, N.J. (1971) Strips: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence, 2, 189-208.[CrossRef]
[27]	Nilsson, N.J. (1980) Principles of Artificial Intelligence. Tioga Publishing Co.
[28]	Nilsson, N.J. (1998) Artificial Intelligence: A New Synthesis. Morgan Kaufmann.
[29]	Ghallab, M., Howe, A., Knoblock, C., McDermott, D., Ram, A., Veloso, M., Weld, D. and Wilkins, D. (1998) PDDL—The Planning Domain Definition Language, Version 1.2. Technical Report CVC TR-98-003/DCS TR-1165. Yale Center for Computational Vision and Control.
[30]	Haslum, P., Lipovetzky, N., Magazzeni, D. and Muise, C. (2019) An Introduction to the Planning Domain Definition Language. Springer.
[31]	Bercher, P., Alford, R. and Höller, D. (2019) A Survey on Hierarchical Planning—One Abstract Idea, Many Concrete Realizations. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, Macao, 10-16 August 2019, 6267-6275.[CrossRef]
[32]	Georgievski, I. and Aiello, M. (2015) HTN Planning: Overview, Comparison, and beyond. Artificial Intelligence, 222, 124-156.[CrossRef]
[33]	Colledanchise, M. and Ögren, P. (2019) Behavior Trees in Robotics and AI: An Introduction. CRC Press.
[34]	Iovino, M., Scukins, E., Styrud, J., Ögren, P. and Smith, C. (2022) A Survey of Behavior Trees in Robotics and AI. Robotics and Autonomous Systems, 154, Article ID: 104096.[CrossRef]
[35]	Kress-Gazit, H., Lahijanian, M. and Raman, V. (2018) Synthesis for Robots: Guarantees and Feedback for Robot Behavior. Annual Review of Control, Robotics, and Autonomous Systems, 1, 211-236.[CrossRef]
[36]	Armstrong-Wright, A.T. (1969) Critical Path Method: Introduction and Practice. Harlow.
[37]	Hansen, B.J. (1964) Practical PERT, Including Critical Path Method. America House.
[38]	Horowitz, J. (1967) Critical Path Scheduling: Management Control through CPM and PERT. Ronald Press Company.
[39]	Levin, R.I. and Kirkpatrick, C.A. (1966) Planning and Control with PERT/CPM. McGraw-Hill.
[40]	Warnick, B. (2022) Possibilistic Hierarchical Task Network. Master’s Thesis, Florida State University, Department of Computer Science.
[41]	Warnick, B. (2022) A Demonstration of Possibilistic Hierarchical Task Networks for Believable Agent Behavior. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 18, 285-287.[CrossRef]