Regression-based Planning with Sensing Actions and Incomplete Information

[Comparison With Other Contingent Planners]     [Comparison With Non-deterministic Planners]    [Download]

Comparison With Other Contingent Planners

General Description:

We present a domain-independent regression contingent planner, namely CPR (Conditional Planning based on Regression), that is capable of generating conditional plans and conformant plans in the presence of sensing actions and incomplete information. CPR's search algorithm (influenced by the best-first search strategy) employs a state-based regression formulation [TBZS04] that is in turn based on the 0-approximation semantics discussed in [SB01]. 

A planning problem considered for CPR is a 4-tuple P = (A,O,I,G) where A is a set of fluents, O is a set of actions, I and G are set of fluent literals that encode what is known in the initial state and what is desired of a goal state, respectively. Note that, the current version of CPR also supports multi-valued domains. Below we illustrate the performance of CPRin comparison with several related contingent planners in the literature. 

Please contact me if you have any questions or comments related to this stuff.

Test Results:

Domains:

GridMineSweep:

There is a grid of size N*N. There are mines at some positions on the grid. There is a robot, also on the grid, which can travel North, South, West, and East one step at a time. It can sense whether a mine safety lock is on or off at some predefined positions on the grid, it can turn the lock to make the lock become on or off alternatively, and disarm the mine at some specific locations. The goal is to make the grid have only disarmed mines without causing explosion. Initially, we know the robot's position, positions that the robot can disarm bomb and sense bombs' lock; but we don't know which mines are not disarmed. This domain may generates many possible plans that have unbalanced tree shape with many non-sensing actions and sensing actions.

Mail-man:

A modified version of the logistics domain used in IPC'02. A variant of the logistics domain is also discussed in [BKS04]. Basically, a central post office must direct their mail men to travel to several locations and cities to collect mails from mail-collection boxes. The transportation is either by car (in a local city) or flight (between cities). The mail men do not know a location has mail or has no mail. So one has to go there and check, then collect if available. Initially, we may know some vehicles whereabouts. This is somehow similar to the GridMineSweep but with more types of traveling.

Results:

Results for CPR using mutex and Max and Sum heuristics, YKA, MBP, POND (using LUG_RP heuristics): Total time in milliseconds. Note that: (i) Both YKA and MBP do not handle sensing actions with preconditions, we  therefore only use observable fluents instead; (ii) MBP running option: -v 0 -explicit_dfs_forward -no_conformant_at_start -no_plan_check. The symbol {-} in the table denotes that we either stop the planner or the planner kills itself after 15 minutes of running.

Downloads:

CPR planner            Domains

CPR uses a Graphical User Interface for easy interaction with the planner. 

• The command line for Windows is: java -cp CPR.jar zeroaprx.CPR
• To run in a Linux/Unix environment, please use with the flag -linux: java -cp CPR.jar zeroaprx.CPR -linux

Comparison With Non-deterministic Planners

Results of running CPR and MBP (with the corresponding 3-valued non-deterministic domains)

Results for CPR using mutex and Max and Sum heuristics, and MBP: Total time in milliseconds. MBP running option: -v 0 -explicit_dfs_forward -no_conformant_at_start -no_plan_check. The symbol {-} in the table denotes that we either stop the planner or the planner kills itself after 15 minutes of running.

** Note: The paper by Cimatti et al [CPRT03] discusses such planners (QBFPLAN by Rintanen, GPT by Bonet and Geffner, SIMPLAN by Kabanza et al, and SGP by Weld et al). Note that, among these non-deterministic planners, MBP is more efficient than QBFPLAN (pages 34 & 35 [CPRT03]) and SGP, MBP is also faster than GPT - a probabilistic planner. SIMPLAN of Kabanza is a domain-dependent planner and thus we don't consider it as ours is a domain-independent planner. Nevertheless, MBP is also faster than SIMPLAN (page 37 [CPRT03]). We therefore only compare our planner's performance with that of MBP.

Downloads:

MBP Domains

Contact Information:

Please contact me if you have any questions or comments related to this stuff.

References

[BKS04] D. Bryce, S. Kambhampati and D. Smith. Planning Graph Heuristics for Belief Space Search. ASU CSE TR. Submitted for journal publication.

[CPRT03] Cimatti, A., Pistore, M., Roveri M., Traverso P. Weak, strong, and strong cyclic planning via symbolic model checking. 
Artificial Intelligence Journal 147(1-2): 35-84 (2003)

[SB01] C. Baral and T. Son. Formalizing sensing actions -- a transition function based approach. In Artificial Intelligence Journal, 125 (1-2), pgs 19-91, Jan 2001.

[TBZS04] Le-Chi Tuan, C. Baral, Xin Zhang, Tran Son. Regression With Respect to Sensing Actions and Partial States. AAAI'04.