Time-Saving Tips for Problem Solving with Incomplete Information

Problem solving with incomplete information is usually very costly, since multiple alternatives must be taken into account in the planning pro cess. In this paper, we present some pruning rules that lead to substantial cost savings. The rules are all based on the simple idea that, if goal achievement is the sole criterion for performance, a planner need not consider one “ branch” in its search space when there is another “ branch” characterized by equal or greater information. The idea is worked out for the cases of sequential planning, conditional planning, and interleaved planning and execution. The rules are of special value in this last case, as they provide a way for the problem solver to terminate its search without planning all the way to the goal and yet be assured that no important alternatives are overlooked. * in a piece of stock, and it decides to do this by using a drill press. The complication is that there might or might not be some debris on the drill press table. In some cases, it may be possible to formulate a sequential plan that solves the problem. One possibility is a sequential plan that covers many states by using powerful operators with the same effects in those states. In our example, the robot might intend to use a workpiece fixture that fits into position whether or not there is debris on the table. Another possibility is a sequential plan that coerces many states into a single known state. For example, the robot could insert into its plan the action of sweeping the table. Whether or not there is debris, this action will result in a state in which there is no debris. A second possibility is for the planner to insert a conditional into the plan, so that the robot will examine the table before acting, in one case (debris present) clearing the table, in the other case (table clear) proceeding without delay.

Authors

• Michael R. Genesereth Illah R. Nourbakhsh

Keywords

No keywords are indexed for this paper.