Abstract:
This paper addresses the problem of deciding effectively whether to interrupt a teammate who may have information that is valuable for solving a collaborative scheduling problem. Two characteristics of multi-agent scheduling complicate the determination of the value of the teammate's information, and hence whether it exceeds the costs of an interruption. First, in many scheduling contexts, task and scheduling knowledge reside in a scheduler module which is external to the agent, and the agent must query that module to estimate the value to the solution of knowing a specific piece of information. Second, the agent does not know the specific information its teammate has, resulting in the need for it to repeatedly query the scheduler. Choosing the right sequence of queries to the scheduler may enable the agent to make an interruption decision sooner, thus saving query time and computational load for both the agent and the external system. This paper defines two new sequencing heuristics which enhance the efficiency of the querying process. It also introduces three metrics for measuring the efficiency of a query sequence. It presents extensive simulation-based evidence that the new heuristics significantly outperform previously proposed methods for determining the value of information a teammate has.