Temporal Reasoning Involving Counterfactuals and Disjunctions

I. Introduction

A critical part of planning involves selecting a plan for achieving a particular task. A reduction type planner (e.g. NOAH [7]), faced with the problern of formulating a plan for the conjunction of two or more nonprimitive tasks, is often forced to make plan selection decisions on the basis of incomplete knowledge. The planner cannot anticipate interactions with tasks whose reduction (or detailed spec­ ification) it has yet to explore. Given that there exists no strong warrant for choosing one plan over another why should a planner make a choice at all? In certain situations it would seem that procrastination is appropriate.

The problern here is similar to one addressed by Sacer­ doti in developing the NOAH planner. NOAH employed a strategy known as least commitment and a data structure known as a procedural net to avoid making ordering deci­ sions until they were warranted by interactions discovered in the course of planning. This was a reaction to previous planners' use of what is called the linear assumption: the tasks in a conjunction of tasks to be solved are assumed to be independent and hence there is no harm in committing to some arbitrary order for the purposes of planning. The problern was that by committing early (and arbitrarily) the planner might have to explore a large nurober of alternative orderings before finding one that worked. Most planners [7] [9] [10] have made a similar assumption as regards plan se­ lection; namely that in the absence of information to the contrary any plan for achieving a task will suffice.

In order to deal with the problems that arise as a result of making this assumption a nurober of strategies have been proposed. NOAH represented alternative plans for achiev­ ing a given task as a disjunction (implicitly exclusive) of plans. The planner expanded the current procedural net with each disjunct noting the type and nurober of inter­ actions: this information served as the basis for choosing among the alternatives. A more general technique employ­ ing a context mechanism was proposed by Wilkins [11]. The problern with both of these approaches is that the planner is responsible for proposing descriptions of the world which follow from making certain decisions (choosing among al­ ternatives). If a planner wanted to make sure it hadn't missed some fortuitous combination of choices it would have to construct and evaluate all such worlds ( combinations of choices). The planner had no way of anticipating good and bad interactions without exploring the alternatives. What was really needed was an efficient method of discovering sets of choices to avoid (those that Iead to problems) and sets of choices to consider seriously (those that consolidate effort).

If you are entertaining a nurober of apparently inde­ pendent alternatives it seems reasonable that you are able to notice interactions, both advantageaus and detrimental, involving sets of these alternatives. Suppose that I have a task of mailing a package and I'm considering either driving to the local UPS depot or using the regular mail service and walking to the post office. If I've recently thought about buying some stamps then I might want to take advantage of the opportunity of being at a location selling stamps afforded by the latter. Of course some consolidations are not possible. A planner must have some means of ignoring deductions based on effects achieved by exclusive alterna­ tives. If you are planning a weekend trip but undecided on whether to spend it in a rural or an urban setting it would be a bit silly to formulate a plan which closely couples a relaxing walk in the countryside with a Broadway show.

In addition to reasoning about alternatives and aspects of the world that the planner has control over, a planner quite often finds itself in the position of reasoning about ways the world might have been had events turned out otherwise (counterfactuals). To reason about methods for preventing some predicted unpleasantness we have to be careful to distinguish the circumstances that prompted us to action from those brought about by our attempts to avoid the predicted events. I might plan to deposit a sum of money in my checking account to avoid the penalty from an overdraft. Having determined to do so it is not likely I will be fined but this shouldn't somehow lessen my resolve to actually carry out the actions required to make the deposit. Silly as this may sound, it requires some sophisti­ cation to avoid just such confusions.

This initial discussion was meant to outline some prob­ lems which have not been handled adequately by previous planning systems. The examples were meant to illustrate a dass of situations which require reasoning about alter­ native, possibly exclusive, descriptions of the world. In the remainder of this paper I will describe a temporal reasoning module designed as part of a planning system which sup­ ports this sort of hypothetical reasoning. This short paper cannot hope to satisfy the curiosity of all and I encourage the interested reader to refer to 121 for a more complete exposition.

II. Planning and temporal reasoning

This section outlines the module used for temporal rea­ soning in the FüRBIN planner I6J. This module is referred to as a time map manager (TMM) IIJ and is loosely based on the representation described in 14]. A time map is a data structure which captures what is known about events occur­ ring over time (e.g. their duration and relative ordering) and the effects of processes and actions (e.g. the persis­ tence or the period of time over which such effects can be said to endure). The time map itself consists of a network whose nodes are points corresponding to the begin and end of what are called time tokens. A time token denotes an interval associated with the occurrence of an event or an instance of a fact being believed to become true and persist for some period. The points in the network are connected by arcs indicating constraints on the distance separating points. A constraint is represented as an interval on the real nurober line denoting an upper and lower bound on the distance separating two points in the time map.

The TMM performs a rather simple sort of temporal reason maintenance. The system uses data dependencies and constraint propagation to ensure that whenever two time tokens asserting Contradietory facts (or mutually ex­ clusive states) are ordered as to their beginning points the earlier will be constrained (or clipped) to end before the later.

Plans generally have prerequisites or facts which must be true in order that the plan be applicable in a given sit­ uation. Plan choice involves selecting a plan and an inter­ val in which that plan's prerequisites are predicted to be true. Having made such a selection the planner creates to­ kens corresponding to the plan steps (subtasks) and their effects, adds them to the time map along with associated constraints, and asserts that the plan is plausible. This as­ sertion is however defeasible. Other tasks might be intro­ duced during subsequent planning that clip the persistence of a prerequisiie fact thereby invalidating the plan. The TMM monitors the continued validity of plausibility as­ sertions by setting up nonmonotonic data dependency jus­ tifications composed of assertions called called protections

(after IBJ). A fact Q is said tobe protected throughout an interval, ptl to pt2, just in case there exists a time token asserting Q that begins before ptl and it's consistent to believe that it doesn't end before pt2.

If a protection fails then the TMM notifies the planner of any plans threatened by the failed protection. The fail­ ure is annotated in such a way as to facilitate corrective action. The TMM also anticipates possible protection fail­ ures and suggests ordering constraints to avoid undesirable interactions.

111. Handling disjunctions

Still the machinery outlined above won't allow us to represent protections of the form "a task T for preventing an event E is warranted just in case E would occur if T didn't". Neither will it allow us to consider more than one reduction for a given task at a time. The latter involves reasoning about disjunctions.

The techniques supporting this sort of rcasoning rely upon a method for computing the choices warranting as­ sertions in the time map. Choices (e.g. alternative plans or ordering decisions) are represented as boolean variables. Each assertion is labeled with a boolean formula indicat­ ing under which choices the assertion is believed. Labels are computed using a method similar to that employed in McDermott's context mechanism I5J. McDermott's system was designed to reason about a )arge nurober of contexts sequentially. It demands that the user specify a partic­ ular context (set of choices) to consider. It is essential to our problern that we be able to reason about many sets of choices simultaneously. The mechanism must also be able to ignore certain sets of choices (e.g. those including exclusive alternatives). The TMM employs techniques sim­ ilar to those used by deKleer I3J to reason about exclusive alternatives and disregard sets of choices no Ionger deemed worth considering. The algorithms are described in detail in 12].

To illustrate how the TMM works in reasoning about choices 1'11 provide an abbreviated example drawn from the machine shop domain. Suppose that the robot operator in a job shop is contracted to machine a special order Hange from a blank casting. The task requires that a certain di­ ameter hole be drilled and one side of the casting be faced (i.e. cut or milled flush). These two subtasks can be per­ formed in any order. Both drilling and facing can be done on either the vertical mill or on the engine lathe. Suppose that the robot chooses to expand the drilling task using two exclusive plans, one using the mill and another using the lathe. 1'11 ignore all subtasks except for prerequisite tasks responsible for installing attachments. Initially the mill has the face milling attachment installed and the lathe has a collet chuck. Drilling on the mill will require a fly cutting attachment while a four jaw chuck is required for drilling on the lathe. The facing task is expanded next and the robot, aided by the TMM, chooses to explore two options: use the lathe, taking advantage of the fact that the four jaw chuck is already in place or use the mill (in this case requiring the collet chuck) and schedule the facing task before the task to install the fty cutter. At the time the facing task alter­ natives are submitted to the TMM it sets up the necessary protections to monitor the tasks' plausibility, and suggests a number of constraints to help avoid protection violations. Notice that while the two tasks, drilling and facing, arestill independent, the plans chosen for them are now very much interlinked. To face using the lathe requires that the robot choose to drill using the lathe. lf the robot chooses to both drill and face using the mill then it must do the facing task first in order to avoid a protection failure.

This just begins to demonstrate the utility of tempo­ ral reasoning about choices. The TMM bandies dependent choices (nested decisions) and provides considerable assis­ tance at plan se!ection time in pointing out options that give rise to advantageaus or disadvantageaus interactions. This same machinery is also used for reasoning about coun­ terfactuals and we'll consider how in the next section.

IV. Complex protectiona

For the most part, in reasoning about hypotbetical sit­ uations, what we want is a virtual copy of some existing situation with just a few changes. For instance suppose that l'm concerned about a situation in wbich I ignore a dozen or so parking tickets and the city tows my car. So I consider anotber situation in which I bribe a city official to indefinitely postpone action on my case. My warrant for paying the bribe depends upon tbe immediate threat of having my car towed. If that threat evaparates (e.g. the news reports a backlog in the bandling of traffic violations which has forced the city to issue amnesty for all offenders) then I should definitely question my motivation for giving money to that official. On the other band if I discover that my method for handling the situation is ineffectual (e.g. the official has been dismissed having been indicted for accept­ ing bribes) then I bad better consider alternative methods.

This sort of reasoning has often been modeled along the !in es of a conditional proof where introducing and discharg­ ing assumptions is considered analogaus to pushing and popping contexts. There are a number of problems with this, most of them stemming from the nonmonotonic char­ acter of reasoning about beliefs changing over time. From a computational point of view conditional proofs cache de­ ductions in order to ease the computational burden in­ curred by continually rederiving the same formulae. Once one allows nonmonotonicity the process of caching is con­ siderably complicated, as all deductions are potentially de­ feasible. A conditional proof in these circumstances must be represented as an ongoing computation. Tbe TMM ban­ dies tbis in terms of reasoning about cboices.

Let's consider the plight of a maintenance robot in a factory who is informed at 8:00AM tbat OSHA (the U.S. government agency concerned with occupational bealtb and safety) will make an inspection of bis factory sametime after 12:00. The robot makes a critical assessment of bis work space, mindful of tbe OSHA rules, notices that tbe main corridor is duttered witb scrap meta!, and predicts tbat be will be fined for tbe safety hazard. The robot tben deter­ mines to clean tbe aisles before noon in order to avoid tbe fine. In order to monitor the warrant for and effectiveness of the task to clean the aisles the TMM tags the token for the clean-up task as a choice. If the robot schedules work that will result in the corridor getting duttered after the clean-up but before the inspection then the TMM will no­ tice that the clean-up task is no Ionger effective. If on the other band someane eise eieans the corridor or the OSHA visit is called oft' tben the clean-up task will no Ionger be warranted. The TMM monitors tbe continued warrant for prevention tasks essentially by considering a world in which the prevention task was never executed.

V. Conclusion

The TMM is applicable in planning domains in which for most tasks the planner has a number of alternative plans and the choice of alternative can make a significant differ­ ence in the efficiency of the composite plan.