2003 | Dana Nau, Tsz-Chiu Au, Okhtay Ilghami, Ugur Kuter, J. William Murdock, Dan Wu, Fusun Yaman
SHOP2 is a domain-independent Hierarchical Task Network (HTN) planning system that excelled in the 2002 International Planning Competition. It received one of the top four awards, including a "distinguished performance" award. The system's success is attributed to its ability to handle temporal and metric planning domains, as well as its efficient planning algorithm and domain-specific knowledge.
SHOP2 generates plans in the order they will be executed, allowing it to know the current state at each step. This reduces uncertainty and enables the system to incorporate substantial expressive power. It supports axiomatic inference, mixed symbolic/numeric computations, and external program calls. SHOP2 also allows tasks and subtasks to be partially ordered, enabling more intuitive domain knowledge representation. It incorporates features from PDDL, such as quantifiers and conditional effects, and can sort alternative methods based on predefined criteria.
SHOP2's planning algorithm uses a forward-chaining approach, decomposing tasks into subtasks recursively. It handles temporal domains by translating PDDL operators into SHOP2 operators that track multiple timelines. The system also includes features like sorting variable bindings, branch-and-bound optimization, and debugging tools. It supports optimization by assigning costs to operators and using branch-and-bound search to find the best plan within time limits.
SHOP2's domain descriptions include methods, operators, and axioms, allowing for complex planning scenarios. It can handle both simple and complex domains, including those with optimization objectives. The system's ability to handle temporal and metric domains, combined with its efficient planning algorithm, made it highly effective in the competition. SHOP2 solved 899 out of 904 problems, achieving a 99% success rate. It was slower than some other planners but performed well in specific domains like Satellite-HardNumeric. The system's success in the competition highlights its effectiveness in planning tasks with temporal and metric constraints.SHOP2 is a domain-independent Hierarchical Task Network (HTN) planning system that excelled in the 2002 International Planning Competition. It received one of the top four awards, including a "distinguished performance" award. The system's success is attributed to its ability to handle temporal and metric planning domains, as well as its efficient planning algorithm and domain-specific knowledge.
SHOP2 generates plans in the order they will be executed, allowing it to know the current state at each step. This reduces uncertainty and enables the system to incorporate substantial expressive power. It supports axiomatic inference, mixed symbolic/numeric computations, and external program calls. SHOP2 also allows tasks and subtasks to be partially ordered, enabling more intuitive domain knowledge representation. It incorporates features from PDDL, such as quantifiers and conditional effects, and can sort alternative methods based on predefined criteria.
SHOP2's planning algorithm uses a forward-chaining approach, decomposing tasks into subtasks recursively. It handles temporal domains by translating PDDL operators into SHOP2 operators that track multiple timelines. The system also includes features like sorting variable bindings, branch-and-bound optimization, and debugging tools. It supports optimization by assigning costs to operators and using branch-and-bound search to find the best plan within time limits.
SHOP2's domain descriptions include methods, operators, and axioms, allowing for complex planning scenarios. It can handle both simple and complex domains, including those with optimization objectives. The system's ability to handle temporal and metric domains, combined with its efficient planning algorithm, made it highly effective in the competition. SHOP2 solved 899 out of 904 problems, achieving a 99% success rate. It was slower than some other planners but performed well in specific domains like Satellite-HardNumeric. The system's success in the competition highlights its effectiveness in planning tasks with temporal and metric constraints.