A better understanding of more structured instances, as they occur in actual applications, is needed. That is, little or no domain- specific search control knowledge is used. This kind of reasoning or search generally requires substantial computational resources. There are interesting tradeoffs to be explored between the cost of preprocessing and on-line savings. Challenge applications in planning, operations research, learning, and computational biology.
Planning is a notoriously hard combinatorial search problem.
Recent planners, based on reformulating planning in terms of large constraint satisfaction problems, can find plans with several hundred operations. The next step is to develop planners that synthesize sequences of thousands of steps. This would lead to new applications in areas as diverse as protocol verification, supply-chain management, and program synthesis. Other promising areas of application of compute-intensive methods are in machine learning, operations research, and computational biology.