The Use of Multiple Problem Decompositions in Time Constrained Planning Tasks

Abstract

Problems requiring thc synthcsis of a collection of plans accomplishing distinct (but possibly related) goals has received incrcasing attention within Al. Such problcms arc typically formulated as multi·agcnt planning problems, cmphasizing a problern decomposition \\'herein individual agents assumc responsibility for the gencration of individual plans whilc taking ir.to account the goals and beliefs of other agents in the system. One conscqucnce of such a problern decomposition is a simplified view of resource allocation that assumcs avoidance of conflicts to be the sole concern. The validi ty of this assumplion comes into qucstion in time constrained problern domains rcquiring the allocation of multiple, shared resources. In job shop schcduling, for example, where sequences of manufacturing Operations must be detcrmined 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 perspcctives is essential to appropriate consideration of all domain constraints.