Abstract
In this paper, we study the problem of achieving efficient interaction in a distributed scheduling system whose scheduling agents may borrow resources from one another. Specifically, we expand on Sycara's use of resource texture measures in a distributed scheduling system with a central resource monitor for each resource type and apply it to the decentralized case. We show how analysis of the abstracted resource requirements of remote agents can guide an agent's choice of local scheduling activities not only in determining local constraint tightness, but also in identifying activities that reduce global uncertainty. We also exploit meta-level information to allow the scheduling agents to make reasoned decisions about when to attempt to solve impasses locally through backtracking and constraint relaxation and when to request resources from remote agents. Finally, we describe the current state of negotiation in our system and discuss plans for integrating a more sophisticated cost model into the negotiation protocol. This work is presented in the context of the Distributed Airport Resource Management System, a multi-agent system for solving airport ground service scheduling problems.
Introduction
In complex logistical environments, such as managing ground services at a major airport, scheduling is more than a computational optimization problem; it is a challenge of distributed coordination. When multiple autonomous agents—each responsible for specific flights and resources—must cooperate, they face a fundamental dilemma: when should an agent resolve a conflict through local backtracking, and when should it reach out to borrow resources from a peer?
Traditional centralized scheduling often fails in these environments due to the high overhead of maintaining a global state and the proprietary nature of agent data. Conversely, purely decentralized systems often suffer from "myopic" decision-making, where an agent solves a local constraint in a way that inadvertently creates a bottleneck for the rest of the system. This research introduces a framework for using "meta-level information" to bridge this gap, providing agents with a "weather map" of system-wide resource demands to guide local actions.
Methodology and System Architecture
The research is implemented within the Distributed Dynamic Scheduling System (DIS-DSS) and evaluated using the Distributed Airport Resource Management (DIS-ARM) testbed. The core of the approach relies on three primary mechanisms:
1. Texture Measures and Demand Profiles
Building on the work of Katia Sycara, the authors utilize "texture measures" to represent resource contention. Agents generate demand profiles—abstracted summaries of their expected resource needs (e.g., fuel trucks or baggage tugs) over specific time intervals. By exchanging these profiles, agents build a "Lending Possibilities" map, identifying periods of surplus or scarcity across the network without sharing sensitive, low-level schedule details.
2. Stratified Goal Rating
To manage their internal agendas, agents employ a five-level priority scheme that incorporates both local constraints and predicted global needs:
- Tightly constrained goals that require resource borrowing to be feasible.
- Tightly constrained local goals that can be solved internally.
- Remote requests from other agents that overlap with local resource needs.
- Loosely constrained tasks with high flexibility.
- Tasks conflicting with predicted remote needs, which are deferred to avoid premature commitments that might block a more critical global requirement.
3. Dynamic Negotiation Planning
Agents use the meta-level map to treat negotiation as a strategic search. If the global map indicates that a resource is "tight" across all agents, the system avoids futile communication and immediately initiates local backtracking or constraint relaxation. If a surplus is detected elsewhere, the agent initiates a negotiation protocol to borrow the necessary resource.
Experimental Evaluation
The system was tested using six scenarios in the DIS-ARM environment, involving 10 to 60 service orders (e.g., cleaning, fueling, baggage handling) distributed among three autonomous agents. Resources were allocated such that inter-agent cooperation was necessary for successful schedule completion.
Key Findings
- Reduction of Global Uncertainty: By deferring non-critical local tasks that were predicted to conflict with remote needs, agents significantly reduced the likelihood of system-wide bottlenecks.
- Communication Efficiency: The study found that a specific resource request carries more information than a general texture profile. Prioritizing the processing of these remote requests allowed the system to settle global constraints more rapidly.
- Performance Trade-offs: While the distributed system produced slightly lower-quality schedules compared to a theoretical fully centralized controller, the inclusion of meta-level information significantly narrowed this gap and outperformed "opportunistic" schedulers that ignored global context.
Discussion and Future Work
The use of meta-level information allows autonomous agents to make reasoned decisions about the trade-offs between local computation (backtracking) and social interaction (negotiation). However, the current model assumes static service orders. In a live airport environment, dynamic variables such as flight delays or equipment failure would require more frequent updates to the meta-level "map."
Future research directions include the integration of sophisticated cost models—such as the financial impact of missed flight connections—into the negotiation logic, and the development of protocols that allow agents to "renege" on resource loans if their local situation changes drastically, necessitating a form of global backtracking.
Summary updated