📄 Learning and executing generalized robot plans

Summary

The paper extends two components of an SRI mobile-robot system: the planner STRIPS and the execution monitor PLANEX. Their tasks include pushing boxes between rooms and passing through doors. Before this work, every plan was built from scratch. A failure during execution also forced the robot to repeat exactly the same steps. The authors add a generalization stage that replaces the problem-specific constants in a finished STRIPS plan with parameters, so one plan covers a family of tasks. The result is stored in a triangle table, which records the conditions under which each remaining tail of the plan still works. Stored plans, called MACROPs, are used in two ways. STRIPS treats a whole MACROP, or a fragment of it, as a single macro operator when solving new problems. PLANEX uses the same structure to choose a new binding of the parameters when the world differs from expectations. Experiments show plans accumulating into long sequences that STRIPS could not otherwise find. The work is an early demonstration of learning inside automated planning.

Key points

• Operator model: STRIPS describes each operator by a precondition wff, an add list and a delete list. It proves goals with the QA3 resolution theorem prover.
• Triangle table: this format exposes most of the 2^n − 1 legitimate subsequences of an n-step plan, so any of them can be reused as a unit. Its "kernels" give the preconditions for executing the remaining part of a plan.
• Robust execution: in a seven-room test environment, a box blocked a door. PLANEX re-instantiated the generalized plan and sent the robot through a different room to reach its target.
• Long plans: a sequence of eight learning problems produced a 19-operator MACROP that fetches three boxes from three rooms and pushes them together. It absorbed the seven earlier MACROPs.
• Open problems: the authors name three. Preconditions need to be abstracted so large macros stay tractable, old plans need to be forgotten, and operator models should be corrected from observed behavior. (Artificial Intelligence 3, 1972, pp. 251–288.)