Task-network planning using total-order forward search, and applications to bridge and to microwave module manufacture

Because most real-world planning problems are difficult, AI planning researchers have needed to make simplifying assumptions in order to solve some of these problems at all. These simplifying assumptions eliminated some of the difficult features that need to be considered to solve other problems. For example, in existing AI planning algorithms, the approaches to dealing with uncertainty and numerical values are insufficient to handle many important problems. To address these limitations, I have developed a new variant of Hierarchical Task Network (HTN) planning, which I call planning using TOFS (Total-Order Forward Search). In TOFS, a planner always instantiates the operators in a plan in the order that they will be executed. I have applied TOFS successfully to two very different real-world problems. (1) The first problem was play of declarer's cards at contract bridge. My implementation of HTN planning using TOFS, called Tignum 2, does statistically significantly better than the best available computer bridge program. (2) The second problem was automated process planning for the manufacture of microwave modules. My implementation of HTN planning using TOFS, called the EDAPS Process Planner, incorporates electronic and mechanical manufacturing processes, works concurrently with an electronic CAD tool, and provides feedback about manufacturability and lead time to the designers, based on actual process plans for the manufacture of the device. In both domains, HTN planning using TOFS ran relatively quickly, and searched relatively few nodes. In this dissertation, I describe HTN planning using TOFS, its application to these two domains, and consequent observations. I detail the adaptations of HTN planning using TOFS required to apply it to bridge, and the adaptations required to apply it to microwave module manufacture. I observe that TOFS allows the preconditions of methods to be written with arbitrary computer code, and discuss the advantages and disadvantages of this technique. Because both research projects were successful, I am confident that HTN planning using TOFS is an important new AI planning methodology. To reap the benefits of HTN planning using TOFS, a classification of domains into those for which it is suitable and those for which it is unsuitable must be further developed.