Planning with Sharable Resource Constraints

Abstract

When planning systems deal with realistic domains, they must cope with a large variety of constraints imposed by the environment such as temporal or resource constraints. The robustness of the generated plan is a direct consequence of a correct handling of these constraints. We argue that increasing the expressiveness of a representation can be achieved without fundamentally affecting the global efficiency of the search. This paper presents a temporal planner, IxTeT, which integrates sharable resource management into the process of plan generation. In IxTeT, planning operators are described as temporal structures of conditions, effects and sharable resource uses. During the search, pending subgoals, protection threats and resource conflicts are detected by three flaw analysis modules. The detection of sharable resource conflicts is performed thanks to an efficient clique-search algorithm on a possible intersection graph . The control of the search is based on a least-commitment opportunistic strategy. Our approach has been implemented, tested and shown to be satisfactory in various application ·domains.