The TALplanner Project

TALplanner is a forward-chaining planner based on the use of rich domain knowledge to constrain and prune the standard forward-chaining search tree, originally inspired by the planner TLPlan. Such domain knowledge can consist of common-sense information about which occurrences or state sequences are unreasonable in given circumstances. As a simple example, flying an unmanned aerial vehicle to a particular destination makes no sense if the current fuel level will not suffice for a return to a refueling location, even though it would be physically possible to perform that first flying action. Given a variety of such rules, the search tree may be pruned to a degree where one can very efficiently find a solution using standard uninformed search methods.

The domain knowledge used by TALplanner, as well as all other information about a planning domain and problem instance, is represented as logic formulas in a version of TAL, Temporal Action Logics. TAL is a highly expressive family of narrative-based linear metric time logics used for reasoning about action and change in incompletely specified dynamic environments, and has proven to be very suitable for use in planning.

A TAL goal narrative provides a complete domain specification and problem specification, including domain knowledge in the shape of control formulas. TALplanner takes a goal narrative as input and pre-processes it, after which it applies a forward-chaining search procedure that incrementally builds and extends partial interpretations. Throughout this process, the planner continuously and incrementally tests whether control formulas are violated by the current partial interpretation, in which case backtracking is necessary. The TAL logic is used both as a specification language, providing a formal semantics, and as a logic where entailment checks play an important part in the planning procedure. The end result is a TAL plan narrative that entails not only the goal but also all control formulas, permitting such formulas to also be used as a form of temporally extended goals.

TALplanner can generate both concurrent and sequential temporal plans and has support for metric resource constraints. Plans can be annotated with constraints to be tested at execution time by an execution monitoring system, implemented as part of the DyKnow knowledge processing middleware service. The approach and its implementation have proven highly efficient and extensible, and the planner has won awards in international planning competitions. The planner implementation also serves as a basis for new research in extending the expressivity of plans and domain knowledge.

Applications

TALplanner is actively used for planning on board the UASTech UAV. A hardware-in-the-loop simulator is also used to test mission planning for scenarios such as the emergency service logistics scenario.

Awards

TALplanner competed in the planning competition at the Fifth International Conference on Artificial Intelligence Planning and Scheduling Systems (AIPS-2000). It won the domain-dependent planning competition (distinguished planner award) in addition to receiving 1st place in a competition involving the Schindler Miconic elevator control domain, sponsered by Schindler Lifts, Ltd. You can find a description of the competition and the results at the AIPS2000 planning competition web pages.

Publications

Page responsible: Patrick Doherty
Last updated: 2014-04-30