Robot Planning

notes by: Eyal Amir February 7, 1996

This is a summary of [McDermott 92]

1 Robot Programming

• Robots have programs

• Mission, Sensors, Effectors, Program

• Specials:

– Real Time respons

– Changing environment

– Concurrency

– Objects beyond the computer

2 Robot Planning

• The plan

• Planning

• The planning problem

3 Robot Planners

3.1 Minimalism

• Plan, Step, Plan, Step, ... (“Use the world as its own best model”). E.g., SONJA (Chapman 90)

• Abstract Specification → Minimalist Plan. E.g., GAPPS (Kaelbling 88) – Synchronous vs asynchronous plans.

– Combining plans in REX

– A Plan Library

3.2 Plan Interpreters

• Checking effects in a Sequence

• Constraints

• Annotations

• Variables bind to Effective Designators.

• Acquiring: EQUATE; Tracking (Firby 89)

3.3 Theories of Time-Constrained Planning

McDermott: True planning requires generating, opimizing, or, at least, choosing among plans. 3.3.1 Nonlinear planning - Action Graphs

• Action-Graphs

• Plan-Graphs – violator before

– violator after

– goals into new/used actions

• Practicality - constraint satisfaction

• Reducing Interaction 3.3.2 Nonlinear Planning - Libraries

• Plan reduction using libraries

• Combining [concurrent] subplans 3.3.3 Time Constraints

• An anytime algorithm (Dean and Boddy 88)

• How better will it get?

• How usefull will it be?

• Find the best time – Time for decision is negligible

– Delibaration causes only loss of effectiveness – Possible to quantify

3.4 Transformational Planning

3.4.1 Transformations • The need to revise a plan

• Revising as Backtracking

• Pushing a plan in a given direction

• Elaborating abstract plans (Hammond 88,90) and (Simons 88) – Proof → Problem

– Repairs: Steps and values

• More transformations – Reordering Steps

– Adding Timing Constraints

– The “famous” bomb in the toilet (Mcdermott 87) 3.4.2 Plan revision and Planning under time constraints

• How fast is transformational planning?

– The transformation

– The debugging

– Assumptions: The plan is almost correct; Planning pays off (Zweben,Deal,Gargan

90)

• How can transformational planning be combined with execution? – Replacing vs Adjusting

– Plan & Execute Concurrently

– Changing world ⟺ quiescent state.

3.5 Motion Planning

Complete environment description • Configuration Space

• Physics

• Find a path; Stay near it

• The Artificial Potential Field Approach to motion

3.6 Learning

Learning the statistics of the domain.

• Deterministic vs Stochastic

• Stationary vs Nonstationary

• Binary vs Graded

• Immediate vs Delayed

• Memoryless vs State dependent GTRL (Kaelbling 90)

References

[McDermott 92] Drew McDermott, Robot Planning, AI magazine, vol. 13 (2), 1992, 55-79.

This is /u/eyal/ongo/quals/robot plan.tex.