Efficiently handling temporal knowledge in an HTN planner
Published 6 June 2006
Luis Castillo, Juan Fernández-Olivares, Óscar García-Pérez, Francisco Palao
Citations79
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
New features include a sound partial order metric structure, deadlines, temporal landmarking or synchronization capabilities built on top of a Simple Temporal Network and an efficient constraint propagation engine boosted by exploiting the causal structure of plans.
Abstract
This paper presents some enhancements in the temporal reasoning of a Hierarchical Task Network (HTN) planner, named SIADEX, that, up to authors knowledge, no other HTN planner has. These new features include a sound partial order metric structure, deadlines, temporal landmarking or synchronization capabilities built on top of a Simple Temporal Network and an efficient constraint propagation engine boosted by exploiting the causal structure of plans.
Keywords
Computer Science
Communications of the ACMMaintaining knowledge about temporal intervals
7,550 Citations1983James F. Allen
An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation, which is notable in offering a delicate balance between space and time.
Artificial IntelligenceTemporal constraint networks
1,800 Citations1991Rina Dechter, Itay Meiri +1 more
It is shown that the STP, which subsumes the major part of Vilain and Kautz's point algebra, can be solved in polynomial time and the applicability of path consistency algorithms as preprocessing of temporal problems is studied, to demonstrate their termination and bound their complexities.
Constraint Processing
1,514 Citations2003Rina Dechter
Journal of Artificial Intelligence ResearchSHOP2: An HTN Planning System
937 Citations2003Dana Nau, Tsz-Chiu Au +5 more
The features of SHOP2 which enabled it to excel in the competition are described, especially those aspects of SHop2 that deal with temporal and metric planning domains.
AI MagazineAn Introduction to Least Commitment Planning
586 Citations1994Daniel S. Weld
A progression of least commitment planners is summarized, starting with one that handles the simple STRIPS representation and ending with UCPOP, a planner that manages actions with disjunctive precondition, conditional effects, and universal quantification over dynamic universes.
CERN Document Server (European Organization for Nuclear Research)Practical Planning: Extending the Classical AI Planning Paradigm
517 Citations1988David E. Wilkins
IEEE Intelligent SystemsMAPGEN: mixed-initiative planning and scheduling for the Mars Exploration Rover mission
195 Citations2004Mitchell Ai-Chang, J. A. Yglesias +11 more
MAPGEN is the first AI-based system to control a space platform on another planet's surface and discusses the issues arising from combining these tools in this mission's context.
A planning heuristic based on causal graph analysis
184 Citations2004Malte Helmert
This paper proposes translating STRIPS problems to a planning formalism with multi-valued state variables in order to expose this underlying causal structure of the domain, and shows how this structure can be exploited by an algorithm for detecting dead ends in the search space and by a planning heuristic based on hierarchical problem decomposition.
Planning with sharable resource constraints
181 Citations1995Philippe Labone, Malik Ghallab
This paper presents a temporal planner, LxTeT, which integrates sharable resource management into the process of plan generation and argues that increasing the expressiveness of a representation can be achieved without fundamentally affecting the global efficiency of the search.
AI MagazineA Call for Knowledge- Based Planning
117 Citations2001David E. Wilkins, Marie desJardins
The terms knowledge-based and primitive-action planning are defined and an analogy from the current focus of the planning community on disjunctive planners to the experiences of the machine learning community over the past decade is drawn.
O Plan an Open Architecture for Command Planning and Control
68 Citations2006Austin Tate, Brian Drabble +1 more
A close coupling of planning and time or resource scheduling is therefore possible within a system employing an activity based plan representation.
Artificial IntelligenceIntegrating actions and state constraints: A closed-form solution to the ramification problem (sometimes)
57 Citations2000Sheila A. McIlraith
This paper presents an axiomatic closed-form solution to the frame, ramification and qualification problems for a common class of theories and presents a semantic specification for a solution in terms of a prioritized minimization policy, and shows that the successor state axioms of the closed- form solution adhere to this specification.
Bringing users and planning technology together experiences in SIADEX
49 Citations2006Juan Fernández-Olivares, Luis Castillo +2 more
This work describes the solutions adopted to the problems tackled during the development of SIADEX, an intelligent planning and scheduling application where users play a central role in a service oriented architecture devoted to support decisions on crisis intervention planning.
PASSAT: A User-centric Planning Framework
46 Citations2002Karen L. Myers, W. Mabry Tyson +3 more
A plan-authoring system called PASSAT (PlanAuthoring System based on Sketches, Advice, and Templates) that combines interactive tools for constructing plans with a suite of automated and mixed-initiative capabilities designed to complement human planning skills is described.
PLANET: A Shareable and Reusable Ontology for Representing Plans
46 Citations2000Yolanda Gil, Jim Blythe
This paper presents PLANET, an ontology for representing plans, and describes several specializations of it to represent plans in three different real-world domains that were made by adding minor extensions to PLANET’s general definitions and classes.
Strathprints: The University of Strathclyde institutional repository (University of Strathclyde)Extending the exploitation of symmetries in planning
45 Citations2002Maria Fox, Derek Long
This paper extends the symmetry exploitation ideas described in Fox & Long 1999 to handle new symmetries and report results obtained from a range of planning problems.
Exploiting the structure of hierarchical plans in temporal constraint propagation
8 Citations2005Neil Yorke‐Smith
This paper describes a means to exploit the structure of a HTN plan in performing temporal propagation on an associated Simple Temporal Network, and results indicate an order of magnitude improvement on real-world plans.
Planning tourist visits adapted to user preferences
2 Citations2002Susana Fern, Laura Sebastiá +1 more
This paper focuses on the planning part of the project showing the difficulties that entail to solve a real problem with AI planning and proposing a system that overcomes them.