Time-Saving Tips for Problem-Solving with Incomplete Information

July 1993

Time-Saving Tips for Problem-Solving with Incomplete Information

Authors:

Michael Genesereth and Illah Nourbakhsh

Abstract:

Problem solving with incomplete information is usually very costly, since multiple alternatives must be taken into account in the planning process. 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.
@conference{Genesereth-1993-15909,
author = {Michael Genesereth And Illah Nourbakhsh},
title = {Time-Saving Tips for Problem-Solving with Incomplete Information},
booktitle = {Proceedings of 11th National Conference on Artificial Intelligence (AAAI '93)},
year = {1993},
month = {July},
pages = {724 - 730},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.