Robert P. Goldman

AIJ Journal 2014 Journal Article

Plan aggregation for strong cyclic planning in nondeterministic domains

• Ron Alford
• Ugur Kuter
• Dana Nau
• Robert P. Goldman

We describe a planning algorithm, NDP2, that finds strong-cyclic solutions to nondeterministic planning problems by using a classical planner to solve a sequence of classical planning problems. NDP2 is provably correct, and fixes several problems with prior work. We also describe two preprocessing algorithms that can provide a restricted version of the symbolic abstraction capabilities of the well-known MBP planner. The preprocessing algorithms accomplish this by rewriting the planning problems, hence do not require any modifications to NDP2 or its classical planner. In our experimental comparisons of NDP2 (using FF as the classical planner) to MBP in six different planning domains, each planner outperformed the other in some domains but not others. Which planner did better depended on three things: the amount of nondeterminism in the planning domain, domain characteristics that affected how well the abstraction techniques worked, and whether the domain contained unsolvable states.

ICAPS Conference 2010 Conference Paper

Shopper: A System for Executing and Simulating Expressive Plans

• Robert P. Goldman
• John Maraist

We present Shopper, a plan execution engine that facilitates experimental evaluation of plans and makes it easier for planning researchers to incorporate replanning. Shopper interprets the LTML plan language, which extends PDDL in two major ways: with more expressive control structures, and with support for semantic web services modeled on OWL-S. LTML's command structures include not only conventional ones such as branching, iteration, and procedure calls, but also features needed to handle HTN plans, such as precondition-filtered method choice. Unlike conventional programming languages, LTML supports interaction with the agent's belief store, so that its execution semantics line up with those assumed by planners. LTML actions extend PDDL actions in having outputs as well as effects, which means that they can support actions that sense the world; an important special case of this is semantic web services, which reveal information about a state hidden from the agent. To support experimentation as well as action in the real world, Shopper accommodates multiple, swappable implementations of its primitive action API. For example, one may interact with real web services through SOAP and WSDL, or with simulated web services through local procedure calls. We describe novel features of LTML, the interpretation strategy, swappable back-ends, and the implementation.

AIJ Journal 2009 Journal Article

A probabilistic plan recognition algorithm based on plan tree grammars

• Christopher W. Geib
• Robert P. Goldman

We present the PHATT algorithm for plan recognition. Unlike previous approaches to plan recognition, PHATT is based on a model of plan execution. We show that this clarifies several difficult issues in plan recognition including the execution of multiple interleaved root goals, partially ordered plans, and failing to observe actions. We present the PHATT algorithm's theoretical basis, and an implementation based on tree structures. We also investigate the algorithm's complexity, both analytically and empirically. Finally, we present PHATT's integrated constraint reasoning for parametrized actions and temporal constraints.

ICAPS Conference 2009 Conference Paper

A Semantics for HTN Methods

• Robert P. Goldman

Despite the extensive development of first-principles planning in recent years, planning applications are still primarily developed using knowledge-based planners which can exploit domain-specific heuristics and weaker domain models. Hierarchical Task Network (HTN) planners capture domain-specific heuristics for more efficient search, accommodate incomplete causal models, and can be used to enforce standard operating procedures. Unfortunately, we do not have semantics for the methods or tasks that make up HTN models, that help evaluate the correctness of methods, or to build a reliable executive for HTN plans. This paper fills the gap by providing a well-defined semantics for the methods and plans of SHOP2, a state-of-the-art HTN planner. The semantics are defined in terms of concurrent golog (ConGolog) and the situation calculus. We provide a proof of equivalence between the plans generated by SHOP2 and the action sequences of the ConGolog semantics. We show how the semantics reflects the distinction between plan-time and execution-time, and provide some simple examples showing how the semantics can support method verification. The semantics provide an implementation-neutral specification for an executive, showing how an executive must treat the plans SHOP2 generates in order to enforce the expected behaviors. Future directions include automated verification of method specifications, automatically generating plan monitors, and plan revision and repair.

ICAPS Conference 2008 Conference Paper

A New Probabilistic Plan Recognition Algorithm Based on String Rewriting

• Christopher W. Geib
• John Maraist
• Robert P. Goldman

This document formalizes and discusses the implementation of a new, more efficient probabilistic plan recognition algorithm called Yet Another Probabilistic Plan Recognizer, (Yappr). Yappr is based on weighted model counting, building its models using string rewriting rather than tree adjunction or other tree building methods used in previous work. Since model construction is often the most computationally expensive part of such algorithms, this results in significant reductions in the algorithm's runtime.

ICAPS Conference 2008 Conference Paper

Using Classical Planners to Solve Nondeterministic Planning Problems

• Ugur Kuter
• Dana S. Nau
• Elnatan Reisner
• Robert P. Goldman

Researchers have developed a huge number of algorithms to solve classical planning problems. We provide a way to use these algorithms, unmodified, to generate strong-cyclic solutions in fully-observable nondeterministic planning domains. Our experiments show that when using our technique with FF and SGPlan (two well-known classical planners), its performance compares quite favorably to that of MBP, one of the best-known planners for nondeterministic planning problems.

ICAPS Conference 2006 Conference Paper

Durative Planning in HTNs

• Robert P. Goldman

This paper provides techniques for hierarchical task network (HTN) planning with durative actions. HTNs can provide useful heuristic guidance to planners, express goals that cannot be expressed in simple first principles planners, and allow plan generation to be limited by external constraints. The decomposition information in HTN plans can also help guide plan execution. This paper provides a method for encoding PDDL Level 3 durative actions in an HTN formalism compatible with the SHOP2 planner. Efficient planning with these actions requires additional search control. We illustrate the utility of the technique with experimental results on the IPC 2004 AIRPORT domain, and explain how SHOP2 methods were written for this domain.

ICAPS Conference 2004 Conference Paper

Guiding Planner Backjumping Using Verifier Traces

• Robert P. Goldman
• Michael J. S. Pelican
• David J. Musliner

In this paper, we show how a planner can use a modelchecking verifier to guide state space search. In our work on hard real-time, closed-loop planning, we use a modelchecker’s reachability computations to determine whether plans will be successfully executed. For planning to proceed efficiently, we must be able to efficiently repair candidate plans that are not correct. Reachability verifiers can return counterexample traces when a candidate plan violates desired properties. A core contribution of our work is our technique for automatically extracting repair candidates from counterexample traces. We map counterexample traces onto a search algorithm’s choice stack to direct backjumping. We prove that our technique will not sacrifice completeness, and present empirical results showing substantial performance improvements in difficult cases. Our results can be applied to other applications, such as automatic design, and manufacturing scheduling.

IROS Conference 2001 Conference Paper

Planning with increasingly complex executive models

• David J. Musliner
• Robert P. Goldman
• Michael J. S. Pelican

We are developing autonomous control systems for mission-critical domains that require hard real-time performance guarantees. To automatically build reactive plans that meet these requirements, we use formal verification (model checking) techniques to assess the quality of plans as they are built. The verification process uses precise timed automaton models of the executive that will run the resulting reactive plan. This reflexive modeling allows our system to formally verify not just that its plans are correct, but that they will be executed correctly.

IROS Conference 2000 Conference Paper

Coordinated deployment of multiple, heterogeneous robots

• Reid G. Simmons
• David Apfelbaum
• Dieter Fox
• Robert P. Goldman
• Karen Zita Haigh
• David J. Musliner
• Michael J. S. Pelican
• Sebastian Thrun

To be truly useful, mobile robots need to be fairly autonomous and easy to control. This is especially true in situations where multiple robots are used, due to the increase in sensory information and the fact that the robots can interfere with one another. The paper describes a system that integrates autonomous navigation, a task executive, task planning, and an intuitive graphical user interface to control multiple, heterogeneous robots. We have demonstrated a prototype system that plans and coordinates the deployment of teams of robots. Testing has shown the effectiveness and robustness of the system, and of the coordination strategies in particular.

ICRA Conference 2000 Conference Paper

Using Model Checking to Guarantee Safety in Automatically-Synthesized Real-Time Controllers

• David J. Musliner
• Robert P. Goldman
• Michael J. S. Pelican

Concerns the development of autonomous, flexible control systems for mission-critical applications such as unmanned aerial vehicles (UAV) and deep space probes. These applications require hybrid real-time control systems, capable of effectively managing both discrete and continuous controllable parameters to maintain system safety and achieve system goals. Using the CIRCA architecture and its state space planner (SSP) for adaptive real-time control systems, these controllers are synthesized automatically and dynamically, online, while the platform is operating. Unlike many other AI planning systems, CIRCA's automatically-generated control plans have strong temporal semantics and provide safety guarantees, ensuring that the controlled system will avoid all forms of mission-critical failure. This paper is intended to convey an intuitive, qualitative understanding of the way CIRCA verifies its plans using model checking techniques.

UAI Conference 1999 Conference Paper

A New Model of Plan Recognition

• Robert P. Goldman
• Christopher W. Geib
• Christopher A. Miller 0001

We present a new abductive, probabilistic theory of plan recognition. This model differs from previous plan recognition theories in being centered around a model of plan execution: most previous methods have been based on plans as formal objects or on rules describing the recognition process. We show that our new model accounts for phenomena omitted from most previous plan recognition theories: notably the cumulative effect of a sequence of observations of partially-ordered, interleaved plans and the effect of context on plan adoption. The model also supports inferences about the evolution of plan execution in situations where another agent intervenes in plan execution. This facility provides support for using plan recognition to build systems that will intelligently assist a user.

AAAI Conference 1997 Conference Paper

Dynamic Abstraction Planning

• Robert P. Goldman
• Kurt D. Krebsbach

This paper describes Dynamic Abstraction Planning (DAP), an abstraction planning technique that improves the efficiency of state-enumeration planners for real-time embedded systems such as CIRCA. Abstraction is used to remove detail from the state representation, reducing both the size of the state space that must be explored to produce a plan and the size of the resulting plan. The intuition behind this approach is simple: in some situations, certain world features are important, while in other situations those same features are not important. By automatically selecting the appropriate level of abstraction at each step during the planning process, DAP can significantly reduce the size of the search space. Furthermore, the planning process can supply initial plans that preserve safety but might, on further refinement, do a better job of goal achievement. DAP can also terminate with an executable abstract plan, which may be much smaller than the corresponding plan expanded to precisely-defined states. Preliminary results show dramatic improvements in planning speed and scalability.

ICAPS Conference 1996 Conference Paper

Expressive Planning and Explicit Knowledge

• Robert P. Goldman
• Mark S. Boddy

We are concerned with the implications and interactions of three common expressive extensions to classical planning: conditional plans, context-dependent actions, and nondeterministic action outcomes. All of these extensions have appeared in recent work, sometimes in conjunction, but the semantics of the combination has not been fully explored. As we have argued in previous work, providing a coherent semantics for conditional planning with context-dependent actions requires that the planner’s information state be modeled separately from the world state. In this paper, we present a new planning language, WCPL, encompassing these extensions. The semantics of WCPL includes an explicit treatment of the planner’s information state as knowledge, as opposed to some form of context labelling. In addition to clarifying and unifying a disparate set of results from earlier work, we extend that work: WCPL handles both conditional and fail-safe plans for an action representation including both context-dependent and nondeterministic actions.

ICAPS Conference 1994 Conference Paper

Conditional Linear Planning

• Robert P. Goldman
• Mark S. Boddy

In this paper we present a sound and complete lln. ear planning algorithm which accomodatesconditional actions: actions whose effects cannot be predkted with certainty. Coaditioaal liaear planain8 is si~ificantly simpler than conditional non-linear plannin8 in conception and implementation. Furthermore, the eflldency tradeol which favor non-linear planning do not n~__~__rilycarry over with the same force to planning with conditional actions. Wehave applied our conditional linear planner, PLINTH, to the pmblent of planning imagepmc__*J~_’_ug actions for NASA’s Earth Observing System. Wediscuss the extension of PLm’mto probtbilktic planning.

UAI Conference 1994 Conference Paper

Epsilon-Safe Planning

• Robert P. Goldman
• Mark S. Boddy

AIJ Journal 1993 Journal Article

A Bayesian model of plan recognition

• Eugene Charniak
• Robert P. Goldman

We argue that the problem of plan recognition, inferring an agent's plan from observations, is largely a problem of inference under conditions of uncertainty. We present an approach to the plan recognition problem that is based on Bayesian probability theory. In attempting to solve a plan recognition problem we first retrieve candidate explanations. These explanations (sometimes only the most promising ones) are assembled into a plan recognition Bayesian network, which is a representation of a probability distribution over the set of possible explanations. We perform Bayesian updating to choose the most likely interpretation for the set of observed actions. This approach has been implemented in the Wimp3 system for natural language story understanding.

KER Journal 1992 Journal Article

From knowledge bases to decision models

• Michael P. Wellman
• John S. Breese
• Robert P. Goldman

Abstract In recent years there has been a growing interest among AI researchers in probabilistic and decision modelling, spurred by significant advances in representation and computation with network modelling formalisms. In applying these techniques to decision support tasks, fixed network models have proven to be inadequately expressive when a broad range of situations must be handled. Hence many researchers have sought to combine the strengths of flexible knowledge representation languages with the normative status and well-understood computational properties of decision-modelling formalisms and algorithms. One approach is to encode general knowledge in an expressive language, then dynamically construct a decision model for each particular situation or problem instance. We have developed several systems adopting this approach, which illustrate a variety of interesting techniques and design issues.

UAI Conference 1992 Conference Paper

Integrating Model Construction and Evaluation

• Robert P. Goldman
• John S. Breese

UAI Conference 1990 Conference Paper

Dynamic construction of belief networks

• Robert P. Goldman
• Eugene Charniak

We describe a method for incrementally constructing belief networks. We have developed a network-construction language similar to a forward-chaining language using data dependencies, but with additional features for specifying distributions. Using this language, we can define parameterized classes of probabilistic models. These parameterized models make it possible to apply probabilistic reasoning to problems for which it is impractical to have a single large static model.

UAI Conference 1989 Conference Paper

Plan Recognition in Stories and in Life

• Eugene Charniak
• Robert P. Goldman

Plan recognition does not work the same way in stories and in "real life" (people tend to jump to conclusions more in stories). We present a theory of this, for the particular case of how objects in stories (or in life) influence plan recognition decisions. We provide a Bayesian network formalization of a simple first-order theory of plans, and show how a particular network parameter seems to govern the difference between "life-like" and "story-like" response. We then show why this parameter would be influenced (in the desired way) by a model of speaker (or author) topic selection which assumes that facts in stories are typically "relevant".