Information Technology


Symbolic Pattern Databases in Heuristic Search Planning

AAAI Conferences

This paper invents symbolic pattern databases (SPDB) to combine two influencing aspects for recent progress in domain-independent action planning, namely heuristic search and model checking. SPDBs are off-line computed dictionaries, generated in symbolic backward traversals of automatically inferred planning space abstractions. The entries of SPDBs serve as heuristic estimates to accelerate explicit and symbolic, approximate and optimal heuristic search planners. Selected experiments highlight that the symbolic representation yields much larger and more accurate pattern databases than the ones generated with explicit methods.


On the Identification and Use of Hierarchical Resources in Planning and Scheduling

AAAI Conferences

Many real-world planning applications have to deal with resource allocation problems, and so does planning in the domain of crisis management assistance. In order to support resource allocation in these kind of applications, we present a new approach to the integration of scheduling capabilities and planning. The proposed methodology relies on a hybrid planner, which combines action and state abstraction by integrating hierarchical task network (HTN) planning and state based partial order causal link (POCL) planning into a common framework. We extend the abstraction mechanism of the planner to different kinds of abstraction for resources, namely subsumption, approximation, qualification, and aggregation. We show how these abstractions can be used when modeling the domain and how reasoning about resources can be performed in a flexible way, namely by merging opportunistic planning and scheduling strategies.


The Logic of Reachability

AAAI Conferences

In recent years, Graphplan style reachability analysis and mutual exclusion reasoning have been used in many high performance planning systems. While numerous refinements and extensions have been developed, the basic plan graph structure and reasoning mechanisms used in these systems are tied to the very simple STRIPS model of action. In 1999, Smith and Weld generalized the Graphplan methods for reachability and mutex reasoning to allow actions to have differing durations. However, the representation of actions still has some severe limitations that prevent the use of these techniques for many real-world planning systems. In this paper, we 1) develop a logical notion of reachability that is independent of the particular representation and inference methods used in Graphplan, and 2) extend the notions of reachability and mutual exclusion to more general notions of time and action. As it turns out, the general rules for mutual exclusion reasoning take on a remarkably clean and simple form. However, practical instantiations of them turn out to be messy, and require that we make representation and reasoning choices.


A Plan-Based Personalized Cognitive Orthotic

AAAI Conferences

The majority of reminder systems are inflexible; reminders are issued at static, prespecified times. To be effective, cognitive orthotics should reason about what reminders should be issued and when. This paper describes the personalized cognitive orthotic (PCO), a system that uses plan-based reasoning to attain flexibility. PCO relies on local search techniques to generate high-quality reminder plans based on knowledge of the user's plans and her typical behavior. PCO is being developed in concert with other technologies aimed at improved plan management, including systems that update a user's plans and track action execution. We describe the PCO as it is implemented in the Nursebot application: where it provides timely and relevant reminders to elderly people who have cognitive decline that necessitates assistance in managing their daily activities.


Universal Quantification in a Constraint-Based Planner

AAAI Conferences

We present a general approach to planning with a restricted class of universally quantified constraints. These constraints stem from expressive action descriptions, coupled with large or infinite universes and incomplete information. The approach essentially consists of checking that the quantified constraint is satisfied for all members of the universe. We present a general algorithm for proving that quantified constraints are satisfied when the domains of all of the variables are finite. We then describe a class of quantified constraints for which we can efficiently prove satisfiability even when the domains are infinite. These form the basis of constraint reasoning systems that can be used by a variety of planners.


Plan Representation for Robotic Agents

AAAI Conferences

Most robotic agents cannot fully exploit plans as resources for better problem-solving performance because of imminent limitations of their plan representations. In this paper we propose plan representations that are, for a given job, representationally and inferentially adequate and inferentially and acquisitionally efficient. We state what these properties mean in the context of robotic agents and describe how plan representations can be designed to satisfy them. The proposed plan representations have been successfully employed in several longterm experiments on autonomous robots.


A Knowledge-Based Approach to Planning with Incomplete Information and Sensing

AAAI Conferences

In this paper we present a new approach to the problem of planning with incomplete information and sensing. Our approach is based on a higher level, "knowledge-based", representation of the planner's knowledge and of the domain actions. In particular, in our approach we use a set of formulas from a first-order modal logic of knowledge to represent the planner's incomplete knowledge state. Actions are then represented as updates to this collection of formulas. Hence, actions are being modelled in terms of how they modify the knowledge state of the planner rather than in terms of how they modify the physical world. We have constructed a planner to utilize this representation and we use it to show that on many common problems this more abstract representation is perfectly adequate for solving the planning problem, and that in fact it scales better and supports features that make it applicable to much richer domains and problems.


Estimated-Regression Planning for Interactions with Web Services

AAAI Conferences

"Web services" are agents on the web that provide services to other agents. Interacting with a web service is essentially a planning problem, provided the service exposes an interface containing action definitions, which in fact is an elegant representation of how web services actually behave. The question is what sort of planner is best suited for solving the resulting problems, given that dealing with web services involves gathering information and then acting on it. Estimated-regression planners use a backward analysis of the difficulty of a goal to guide a forward search through situation space. They are well suited to the web-services domain because it is easy to relax the assumption of complete knowledge, and to formalize what it is they don't know and could find out by sending the relevant messages. Applying them to this domain requires extending classical notations (e.g., PDDL) in various ways. A preliminary implementation of these ideas has been constructed, and further tests are underway.


Execution Monitoring with Quantitative Temporal Bayesian Networks

AAAI Conferences

The goal of execution monitoring is to determine whether a system or person is following a plan appropriately. Monitoring information may be uncertain, and the plan being monitored may have complex temporal constraints. We develop a new framework for reasoning under uncertainty with quantitative temporal constraints - Quantitative Temporal Bayesian Networks - and we discuss its application to plan-execution monitoring. QTBNs extend the major previous approaches to temporal reasoning under uncertainty: Time Nets (Kanazawa 1991), Dynamic Bayesian Networks and Dynamic Object Oriented Bayesian Networks (Friedman, Koller, & Pfeffer 1998). We argue that Time Nets can model quantitative temporal relationships but cannot easily model the changing values of fluents, while DBNs and DOOBNs naturally model fluents, but not quantitative temporal relationships. Both capabilities are required for execution monitoring, and are supported by QTBNs.


Speculative Execution for Information Gathering Plans

AAAI Conferences

Although information gathering plans have enabled data from remote heterogeneous sources to be easily combined and queried, their execution performance suffers because access to remote sources is often slow. To address this problem, we have developed a method of speculative execution that increases the degree of run-time parallelism during plan execution. Our approach allows any information gathering plan to be automatically modified to support speculation in a manner that can lead to significant speedups, while ensuring that both safety and fairness are preserved. We demonstrate how speculative execution can be applied to a typical Internet information gathering plan to provide significant performance benefits.