AIICS

Artificial Intelligence & Integrated Computer Systems

LiU » IDA » AIICS

The TALplanner Project

A small problem instance from the Rovers benchmark planning domain, visualized using the TPVis problem visualizer.

Two UASTech UAVs in a test flight area in Revinge, southern Sweden.

A screenshot from the UAV simulation environment, showing plan execution in the emergency services logistics scenario.

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

[11] Patrick Doherty, Jonas Kvarnström, and Fredrik Heintz. A Temporal Logic-based Planning and Execution Monitoring Framework for Unmanned Aircraft Systems. Journal of Autonomous Agents and Multi-Agent Systems, 2009. Published and available online February 2009; print publication forthcoming. [ Journal ]
[10] Jonas Kvarnström, Fredrik Heintz, and Patrick Doherty. A Temporal Logic-Based Planning and Execution Monitoring System. In Jussi Rintanen, Bernhard Nebel, J. Christopher Beck, and Eric Hansen, editors, Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS), Sydney, Australia, September 2008. [ Conference | .pdf ]
[9] Patrick Doherty and Jonas Kvarnström. Handbook of Knowledge Representation, chapter 16, Temporal Action Logics. Elsevier, December 2007. [ Web site | .pdf ]
[8] Jonas Kvarnström. TALplanner and Other Extensions to Temporal Action Logic. PhD thesis, Linköpings universitet, April 2005. Linköping Studies in Science and Technology, Dissertation no. 937. [ .pdf ]
[7] Jonas Kvarnström and Martin Magnusson. TALplanner in the Third International Planning Competition: Extensions and Control Rules. Journal of Artificial Intelligence Research, 20:343-377, December 2003. [ Journal | .pdf ]
[6] Martin Magnusson. Domain Knowledge in TALplanner. Master's thesis, Linköpings universitet, 2003. LiTH-IDA-Ex-02/104. [ .pdf ]
[5] Jonas Kvarnström. Applying Domain Analysis Techniques for Domain-Dependent Control in TALplanner. In Malik Ghallab, Joachim Hertzberg, and Paolo Traverso, editors, Proceedings of the 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS), pages 101-110, Toulouse, France, April 2002. AAAI Press, Menlo Park, California, USA. [ Conference | .pdf ]
[4] Patrick Doherty and Jonas Kvarnström. TALplanner: A Temporal Logic-Based Planner. AI Magazine, 22(3):95-102, August 2001. [ Journal | .pdf ]
[3] Jonas Kvarnström, Patrick Doherty, and Patrik Haslum. Extending TALplanner with Concurrency and Resources. In Werner Horn, editor, Proceedings of the 14th European Conference on Artificial Intelligence (ECAI), volume 54 of Frontiers in Artificial Intelligence and Applications, pages 501-505, Berlin, Germany, August 2000. IOS Press, Amsterdam, The Netherlands. [ Conference | .pdf ]
[2] Jonas Kvarnström and Patrick Doherty. TALplanner: A Temporal Logic Based Forward Chaining Planner. Annals of Mathematics and Artificial Intelligence, 30:119-169, June 2000. [ Journal | .pdf ]
[1] Patrick Doherty and Jonas Kvarnström. TALplanner: An Empirical Investigation of a Temporal Logic-based Forward Chaining Planner. In Claire Dixon and Michael Fisher, editors, Proceedings of the 6th International Workshop on Temporal Representation and Reasoning (TIME), pages 47-54, Orlando, Florida, USA, May 1999. IEEE Computer Society Press. [ Conference | .pdf ]