The Use of Multiple Problem Decompositions in Time-Constrained Planning Tasks

Abstract

Problems requiring the synthesis of a collection of plans accomplishing distinct but mostly related goals has received increasing attention within AI. Such problems are typically formulated as multi-agent planning problems, emphasizing a problem decomposition wherein individual agents assume responsibility for the generation of individual plans while taking into account the goals and beliefs of other agents in the system. One consequence of such a problem decomposition is a simplified view of resource allocation that assumes avoidance of conflicts to be the sole concern. The validity of this assumption comes into question in time constrained problem domains requiring the allocation of multiple, shared resources. In job shop scheduling, for example, where sequences of manufacturing operations must be determine and scheduled for multiple orders, it is necessary to consider much more than availability to efficiently allocate resources over time. We argue that in such domains, an ability to reason from both resource-based and agent-based perspectives is essential to appropriate consideration of all domain constraints.