Looking for Planning Problems Solvable in Polynomial Time via Investigation of Structures of Action Dependencies

Abstract

There are a lot of planning techniques for solving planning problems and many of them solve the planning problems by 'brute force' even though some problems (or parts of them) are easy. An easy planning problem typically has a plan with a specific structure.

The structure described in this paper is based on action dependencies that appear in plans. We are looking for such constraints that are in the plan structures that provide algorithms running in polynomial time.

Keywords

• Looking
• Planning
• Problems
• Solvable
• Polynomial
• Investigation
• Structures
• Action
• Dependencies