Magazine article AI Magazine

TALPlanner: A Temporal Logic-Based Planner

Magazine article AI Magazine

TALPlanner: A Temporal Logic-Based Planner

Article excerpt

Articles

TALPLANNER is a forward-chaining planner that utilizes domain-dependent knowledge to control search in the state space generated by action invocation. The domain-dependent control knowledge, background knowledge, plans, and goals are all represented using formulas in a temporal logic called TAL, which has been developed independently as a formalism for specifying agent narratives and reasoning about them. In the Fifth International Artificial Intelligence Planning and Scheduling Conference planning competition, TALPLANNER exhibited impressive performance, winning the Outstanding Performance Award in the Domain-Dependent Planning Competition. In this article, we provide an overview of TALPLANNER.

TALPLANNER1 (Doherty and Kvarnstrom 1999; Kvarnstrom and Doherty 2001; Kvarnstrom, Doherty, and Haslum 2000) participated in the recent planning competition at the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00), which took place in Breckenridge, Colorado, in April 2000. TALPLANNER received the Outstanding Performance Award in the Domain-Dependent Planning Competition and first place in the Miconic 10 Elevator Control Domain Competition sponsored by Schindler Lifts Ltd. For the domains used in the competition, TALPLANNER exhibited remarkable performance in comparison to many of the other state-of-the-art planners that participated in the competition.

TALPLANNER is a forward-chaining planner that utilizes domain-dependent knowledge to control search in the state space generated by action invocation. The domain-dependent control knowledge, background knowledge, plans, and goals are all represented using formulas in a temporal logic called TAL, which has been developed independently as a formalism for specifying agent narratives and reasoning about them. A narrative consists of a specification of fluents that hold at various points in time, causal dependencies that relate fluent change, action types that characterize action occurrences that can be invoked by an agent, and domain constraints that characterize background knowledge. A logical model for a narrative describes a linear sequence of states where fluents have unique values in each state. A plan is viewed as a narrative, plan operators are viewed as action types, and domain-dependent control knowledge and goals as temporal formulas entailed by the generated narrative.

Although forward-chaining planners generally suffer from a lack of goal directedness when compared to other types of planners such as regression-based or partial-order planners, for many domains, the use of explicitly represented domain-dependent knowledge more than compensates for this deficiency. More significantly, a forward-chaining planner always has a complete description of the past and current states, which facilitates the use of complex operator types with complex preconditions and conditional effects.

The use of a first-order temporal logic language is well suited for compactly representing both the complex operator features and the control knowledge used to prune the search space. This representation is highly amenable to the syntactic transformations used in various types of optimization associated with the planning algorithm. In addition, the use of logic for representation provides a natural semantics for plans, goals, and control knowledge.

How did TALPLANNER come about? As stated previously, we have spent a number of years developing logical representations of agent behaviors in the form of narratives using temporal logic. More recently, we have been involved in an unmanned aerial vehicle (UAV) project that includes development of deliberative-reactive systems to support autonomous behavior. One of the central components of the architecture is a planning module that more often than not must generate plans in a timely or anytime manner. In addition, the planner must have the capability to reason about explicit time and represent actions with complex interactions and duration. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.