A theoretical analysis of conjunctive-goal problems

✍ Scribed by David Joslin; John Roach

• Book ID: 102989346
• Publisher: Elsevier Science
• Year: 1989
• Tongue: English
• Weight: 530 KB
• Volume: 41
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(89)90081-7

✦ Synopsis

Region analysis is a new technique fbr analyzing search problems by applying graph theory to problem state spaces. The analysis here is of search problems, not search algorithms; analyzing problems and classes of problems lets us understand the underlying structure and inherent complexi O, of those problems. The analysis technique is demonstrated in the domain of robot planning problems. Region analysis of conjunctive-goal planning problems gives us a characterization of subgoal interactions that is independent of the problem representation.

We give a formal characterization of nonlinear planning problems, and show that nonlinearity is a weak characterization of the dilficuhy in planning problems.