Incomplete Information
PROBLEM: Values of some state variables are unknown; There are actions capable of sensing (some) of them.
- If k boolean state variables are unknown, then we are in one of 2k initial states
- Two naïve approaches
- PLAN/SENSE/EXECUTE : Solve each of the 2k problems separately; At the execution time sense the appropriate variables, and execute the appropriate plan
- SENSE/PLAN/EXECUTE: First sense the values of the variables. Solve the problem corresponding to the sensed values
- Problems with naïve approaches
- Solving the 2k problems separately is wasteful
- Shared structure (Tree structured plans)
- Not all variables may be observable (or worth observing)
- Conformant planning
- (Find non-sensing plans that work in all worlds)
- Irrelevant variables (Goal directed planning)