Paul Morris

JAIR Journal 2023 Journal Article

Dynamic Controllability of Temporal Plans in Uncertain and Partially Observable Environments

• Arthur Bit-Monnot
• Paul Morris

The formalism of Simple Temporal Networks (STNs) provides methods for evaluating the feasibility of temporal plans. The basic formalism deals with the consistency of quantitative temporal requirements on scheduled events. This implicitly assumes a single agent has full control over the timing of events. The extension of Simple Temporal Networks with Uncertainty (STNU) introduces uncertainty into the timing of some events. Two main approaches to the feasibility of STNUs involve (1) where a single schedule works irrespective of the duration outcomes, called Strong Controllability, and (2) whether a strategy exists to schedule future events based on the outcomes of past events, called Dynamic Controllability. Case (1) essentially assumes the timing of uncertain events cannot be observed by the agent while case (2) assumes full observability. The formalism of Partially Observable Simple Temporal Networks with Uncertainty (POSTNU) provides an intermediate stance between these two extremes, where a known subset of the uncertain events can be observed when they occur. A sound and complete polynomial algorithm to determining the Dynamic Controllability of POSTNUs has not previously been known; we present one in this paper. This answers an open problem that has been posed in the literature. The approach we take factors the problem into Strong Controllability micro-problems in an overall Dynamic Controllability macro-problem framework. It generalizes the notion of labeled distance graph from STNUs. The generalized labels are expressed as max/min expressions involving the observables. The paper introduces sound generalized reduction rules that act on the generalized labels. These incorporate tightenings based on observability that preserve dynamic viable strategies. It is shown that if the generalized reduction rules reach quiescence without exposing an inconsistency, then the POSTNU is Dynamically Controllable (DC). The paper also presents algorithms that apply the reduction rules in an organized way and reach quiescence in a polynomial number of steps if the POSTNU is Dynamically Controllable. Remarkably, the generalized perspective leads to a simpler and more uniform framework that applies also to the STNU special case. It helps illuminate the previous methods inasmuch as the max/min label representation is more semantically clear than the ad-hoc upper/lower case labels previously used.

IJCAI Conference 2005 Conference Paper

Mixed-Initiative Activity Planning for Mars Rovers

• John Bresina
• Ari Jónsson
• Paul Morris
• Kanna

One of the ground tools used to operate the Mars Exploration Rovers is a mixed-initiative planning system called MAPGEN. The role of the system is to assist operators building daily plans for each of the rovers, maximizing science return, while maintaining rover safety and abiding by science and engineering constraints. In this paper, we describe the MAPGEN system, focusing on the mixed-initiative planning aspect. We note important challenges, both in terms of human interaction and in terms of automated reasoning requirements. We then describe the approaches taken in MAPGEN, focusing on the novel methods developed by our team.

IJCAI Conference 2003 Conference Paper

Tractable Pareto Optimization of Temporal Preferences

• LINA KHATIB
• Paul Morris
• Robert Morris
• Kristen Brent Venable

This paper focuses on temporal constraint problems where the objective is to optimize a set of local preferences for when events occur. In previous work, a subclass of these problems has been formalized as a generalization of Temporal CSPs, and a tractable strategy for optimization has been proposed, where global optimality is defined as maximizing the minimum of the component preference values. This criterion for optimality, which we call "Weakest Link Optimization" (WLO), is known to have limited practical usefulness because solutions are compared only on the basis of their worst value; thus, there is no requirement to improve the other values. To address this limitation, we introduce a new algorithm that rc-applies WLO iteratively in a way that leads to improvement of all the values. We show the value of this strategy by proving that, with suitable preference functions, the resulting solutions are Pareto Optimal.

AAAI Conference 2000 Conference Paper

Execution of Temporal Plans with Uncertainty

• Paul Morris

Simple Temporal Networks (STNs) have proved useful in applications that involve metric time. However, many applications involve events whose timing is uncertain in the sense that it is not controlled by the execution agent. In this paper we consider execution algorithms for temporal networks that include events of uncertain timing. We present two such algorithms. The first retains maximum flexibility, but requires potentially costly updates during execution. The second surrenders some flexibility in order to obtain a fast execution comparable to that available for ordinary STNs.

IJCAI Conference 1999 Conference Paper

Managing Temporal Uncertainty Through Waypoint Controllability

• Paul Morris
• Nicola Muscettola

Simple Temporal Networks have proved useful in applications that involve metric time. However, many applications involve events whose timing is not controlled by the execution agent. A number of properties relating to overall controllability in such cases have been introduced in [Vidal and Ghallab, 1996] and [Vidal and Fargier, 1997], including Weak and Strong Controllability. We derive some new results concerning these properties. In particular, we prove the negation of Weak Controllability is NP-hard, confirming a conjecture in [Vidal and Fargier, 1997]. We also introduce a more general controllability property of which Weak and Strong Controllability are special cases. A propagation algorithm is provided for determining whether the property holds, and we identify tractable cases where the algorithm runs in polynomial time. In practice, temporal uncertainty is usually eliminated by padding each uncertain interval with a flexible wait period. For example, a task duration may be modeled as the upper bound of the task's possible executions. In this case, the event at the end of a task does not represent the time at which the task actually ends. Instead, it constitutes a waypoint, i. e. , a time by which we can guarantee that the task has ended. Synchronization with respect to waypoints can now proceed without uncertainty and Simple Temporal Networks are completely adequate. Although this use of waypoints provides a workable solution to the problem of execution uncontrollability, its indiscriminate application may not be desirable or possible. For example, it may obstruct tight synchronization with respect to follow-on requirements. Moreover, it may not be possible to add a wait period after each uncertain delay if several uncontrollable delays are causally connected. In this paper we introduce Waypoint Controllability, a general framework for a formal analysis of when networks that incorporate uncontrollable delays can be successfully executed. Waypoint controllability generalizes the concepts of Strong and Weak Controllability (Vidal and Ghallab, 1996; Vidal and Fargier, 1997]. Roughly speaking, Strong Controllability supplies a guarantee of a fixed execution that works irrespective of the outcomes of the uncontrollable delays, while the absence of Weak Controllability means that there are some outcomes for which no execution will work. Subject to restrictions on the type of network, an algorithm is presented in [Vidal and Ghallab, 1996] that determines Strong Controllability in deterministic polynomial time. It is shown in [Vidal and Fargier, 1997] that the negation of Weak Controllability is in and it is conjectured that the problem is -Complete. We prove here that the negation of Weak Controllability is indeed, This complexity result applies also to Waypoint Controllability, of which Weak Controllability is a special case. Sufficient conditions are presented for the tractability of Waypoint Controllability. From these, we are able to derive the tractability of Strong Controllability while relaxing the restrictions in [Vidal and Ghallab, 1996]. We also provide a propagation algorithm for determining Waypoint Controlla- MORRIS AND MUSCETTOLA 1253

AAAI Conference 1993 Conference Paper

The Breakout Method for Escaping from Local Minima

• Paul Morris

A number of algorithms have recently been proposed that use iterative improvement (a form of hill-climbing) to solve constraint satisfaction problems. These techniques have had dramatic success on certain problems. However, one factor limiting their wider application is the possibility of getting stuck at non-solution local minima. In this paper we describe an iterative improvement algorithm, called Breakout, that can escape from local minima. We present empirical evidence that this method is very effective in cases where previous approaches have difficulty. Although Breakout is not, theoretically complete, in practice it appears to almost always find solutions, for solvable problems. We prove that an idealized (but less efficient) version of the algorithm is complete.

AAAI Conference 1992 Conference Paper

On the Density of Solutions in Equilibrium Points for the Queens Problem

• Paul Morris

There has been recent, interest in applying hillclimbing or iterative improvement methods to constraint satisfaction problems. An important issue for such methods is the likelihood of encountering a non-solution equilibrium (locally optimal) point. We present analytic techniques for determining the relative densities of solutions and equilibrium points with respect to these algorithms. The analysis explains empirically observed data for the n-queens problem, and provides insight into the potential effectiveness of these methods for other problems.

AIJ Journal 1991 Journal Article

Rationality, transitivity, and contraposition

• Michael Freund
• Daniel Lehmann
• Paul Morris

The purpose of this note is to compare the rule of Rational Monotonicity proposed in [3] and different rules expressing some weak forms of Transitivity and Contraposition. We present four weak forms of Transitivity that, in preferential logic, are equivalent to Rational Monotonicity and a weak form of Contraposition that is strictly weaker than Rational Monotonicity but equivalent to it in the presence of Disjunctive Rationality.

AAAI Conference 1988 Conference Paper

Stable Closures, Defeasible Logic, and Contradiction Tolerant Reasoning

• Paul Morris

AAAI Conference 1987 Conference Paper

Curing Anomalous Extensions

• Paul Morris

In a recent paper, Hanks and McDermott presented a simple problem in temporal reasoning which showed that a seemingly natural representation of a frame axiom in nonmonotonic logic can give rise to an anomalous extension, i. e. , one which is counter-intuitive in that it does not appear to be supported by the known facts. An alternative, less formal approach to nonmonotonic reasoning uses the mechanism of a truth maintenance system (TMS). Surprisingly, when reformulated in terms of a TMS, the anomalous extension noted by Hanks and McDermott disappears. We analyze the reasons for this. First it is seen that anomalous extensions are not limited to temporal reasoning, but can occur in simple non-temporal default reasoning as well. In these cases also, the natural TMS representation avoids the problem. Exploring further, it is observed that the form of the TMS justifications resembles that of nonnormal default rules. Nonnormal rules have already been proposed as a means of avoiding anomalous extensions in some non-temporal reasoning situations. It appears that, suitably formulated, they can exclude the anomalous extension in the Hanks- McDermott case also, although the representation does not adjust smoothly to fresh information, as does the TMS. Some variant of nonnormal default appears to be required to provide a correct semantic basis for truth maintenance systems. l

AAAI Conference 1986 Conference Paper

Representing Actions with an Assumption-Based Truth Maintenance System

• Paul Morris

The Assumption-based Truth Maintenance System, introduced by de Kleer, is a powerful new tool for organizing a search through a space of alternatives. However, the ATMS is oriented towards inferential problem solving, and provides no special mechanisms for modeling actions or state changes. We describe an approach to applying the ATMS to the task of representing the effects of actions. The approach extends traditional tree-structured context mechanisms to allow context merges. It also takes advantage of the underlying ATMS to detect inconsistent contexts and to maintain derived results. Some results are presented concerning possible approaches to the treatment of merges in questionable circumstances. Finally, the analysis of actions in terms of a truth maintenance system suggests the need for a more elaborate treatment of contradiction in such systems than exists at present.