Localized Event-Based Reasoning For Multiagent Domains

Abstract

This paper presents the GEM concurrency model and GEMPLAN, a multiagent planner based on this model. Unlike standard state-based AI representations, GEM is unique in its explicit emphasis on events and domain structure. In particular, a world domain is modeled as a set of regions composed of interrelated events. Event-based temporal logic constraints are then associated with each region to delimit legal domain behavior. The GEMPLAN planner directly reflects this emphasis on domain structure and constraints. It can be viewed as a general-purpose constraint satisfaction facility which constructs a network of interrelated events (a “plan’’) that is subdivided into regions (“subplans’’), satisfies all applicable regional constraints, and also achieves some stated goal. Because

GEMPLAN is specifically geared towards parallel, multiagent domains, we believe that its natural application areas will include scheduling and other forms of organizational coordination. GEMPLAN extends and generalizes previous planning architectures in several ways. First of all, it can handle a much broader range of constraint forms than most planners. Second, GEMPLAN’s constraint satisfaction search strategy can be flexibly tuned. A third and critical aspect of our work has been an emphasis on localized reasoning — techniques that make explicit use of domain structure. For example, GEM localizes the applicability of domain constraints and imposes additional “locality constraints’’ on the basis of domain structure. Together, constraint localization and locality constraints provide semantic information that can be used to alleviate several aspects of the frame problem for multiagent domains. The GEMPLAN planner reflects this use of locality by subdividing its constraint satisfaction search space into regional planning search spaces. Utilizing constraint and property localization, GEMPLAN can pinpoint and rectify interactions among these regional search spaces, thus reducing the burden of “interaction analysis’’ ubiquitous to most planning systems.