project overview | components | members | schedule | publications | media | links
Self-Scheduling Systems
In many domains, there is a need for computational frameworks and mechanisms that support dynamic coordination of multiple agents toward achievement of specific global objectives over time. Quite often, the problem at hand centers on allocation of the resources that each agent has at its disposal. For example, different manufacturers along a supply chain have different production capacities and constraints which must be synchronized over time; various commands in a military operation must coordinate and time share the use of their assets; execution of common business processes requires staged participation of personnel in various organizational units.

To better understand and address such multi-agent coordination problems, we are investigating the following issues: (1) Coordination protocols and policies, (2) Use of projection and look-ahead, and (3) Adaptive decision policies.

Our current research in this direction has been focusing on the development of self-scheduling systems that draw on various aspects of a computational model of the self-organizing behavior of wasp colonies. More specifically, we have been developing the following such self-scheduling systems and algorithms:

  1. We have been developing wasp-like agents that we call "routing wasps". These "routing wasps" use adaptive decision policies, patterned after the adaptive behavior of real wasps, for the assignment of jobs to multi-purpose machines faced with sequence-dependent setup constraints. On the real-world application of vehicle paintshop scheduling, these "routing wasps" show superior performance to a "real-world" proven multi-agent system for the problem.

  2. We are also devleoping a stochastic search framework based on the self-organization of dominance hierarchies among wasps in nature. This framework, which we call Wasp beHavior-Inspired STochastic sampLING (WHISTLING), provides a general approach to heuristic-guided stochastic search that utilizes the full potential of the discriminating power of the heuristic for the problem at hand. Underlying WHISTLING is a population of what we call "scheduling wasps" that interact to prioritize the queue of jobs and to search a stochastic neighborhood of the scheduling heuristic.
Routing Wasps

Figure 1: Routing Wasps.

Using a computational model of the self-organized task allocation among wasps in nature, we assign a wasp-like agents called routing wasps to multi-purpose machines (i.e., machines that can process different types of tasks but which may incur some cost to reconfigure itself for some task type given that it finished processing a task of some other type). These routing wasps have response thresholds that adapt over time to provide a mechanism for specialization of machines. Such specialization, when possible, helps minimize the effects of the sequence-dependent setup constraints.
Scheduling Wasps

Figure 1: Scheduling Wasps.

Using a computational model of social hierarchy formation among wasps in nature, we assign wasp-like agents called scheduling wasps to the jobs within a queue. This queue can either may drawn from by a single machine or many machines depending on the structure of the problem. Using the model of dominance contests among real wasps, we use tournaments of dominance contests as a mechanism for randomizing dispatch scheduling policies. Our initial experiments have been in online control scenarios. We have been extending the framework as an iterative stochastic sampling technique that we call Wasp beHavior Inspired STochastic sampLING (WHISTLING).

Future Directions and the FIRE Project

  1. Adaptive Bidding Policies
    The bidding strategies and the wasp task allocation behavior that underpins our routing wasp framework are very similar. Bonabeau, Dorigo, and Theraulaz (1999) pointed out this similarity originally. A high bid for a task is analogous to a low response threshold for that task and a low bid is analogous to a high response threshold. In our recent work, we have expanded on this analogy (Cicirello and Smith, 2001). A low response threshold does not really correspond to a high bid; but rather it corresponds to a high degree of willingness to bid in the first place. And similarly a high response threshold corresponds to a low degree of willingness to bid. Recently, on a real-world vehicle paintshop problem, we have shown that such an adaptive bidding policy has advantages over a simpler policy designed for the problem. For one, it allows the policy to adapt its decisions to the distribution of tasks. Based on such a tracking of the types of tasks, it also allows for agents to choose to refuse to bid on a particular task in anticipation of near-future tasks for which it may be better-suited. It is our desire to implement and compare such an adaptive bidding strategy within the FIRE architecture to other non-adaptive policies.

  2. Distributed Dynamic Self-scheduling Under Synchronization Constraints
    We wish to extend our WHISTLING algorithm to the FIRE domain. WHISTLING provides a fast algorithm for scheduling a set of tasks given an objective you wish to optimize and given a dispatch heuristic for the problem and can be easily used by a single agent to self-schedule its tasks. It is robust to dynamic elements of the problem such as the addition of tasks, the deletion of tasks, and other unexpected events. However, as currently defined, it is not able to handle constraints such as for example if a task needs to be performed in synchronization with a task of another agent.

  3. Fast "Global" Optimization via WHISTLING
    Part of the job of the Leader role in the FIRE architecture is to opportunistically optimize a plan for a set of agents in the world and then sell that new plan back to the agents. WHISTLING may provide an efficient way to do this. All current work with the WHISTLING algorithm has so far concentrated mainly on scheduling by a single agent for a single agent. Scheduling by a single agent for multiple agents is a potential next step.

  4. Fast Algorithm for Assigning Tasks to Bidders
    In the initial definition of the market architecture underlying the FIRE Architecture, Dias and Stentz (tech rept. CMU-RI-TR-01-26) use a simple greedy algorithm for the initial assignment of tasks to bidders to minimize the amount of money paid out by the agent asking for the bids. This greedy algorithm can be the target heuristic for an iterative stochastic search by WHISTLING for a better initial assignment of tasks to bidders.
Key Personnel
©2001 Carnegie Mellon University - Robotics Institute