Coordinating Autonomous Planning Agents with Temporal Constraints

We address the problem of coordinating autonomous agents that have to come up with a joint plan and schedule for a set of tasks. These tasks are interdependent and temporally constrained and are distributed over the agents. We start with investigating the scheduling part of the problem: How to achieve, given the constraints, a joint solution to the distributed scheduling problem where each of the agents is allowed to determine its own schedule for the set of tasks assigned to it. Here, the problem is to ensure that whatever individual schedule each agent comes up with, these schedules always can be combined into a global schedule satisfying all constraints. Next, we investigate a more complex problem where, before scheduling, the agents are allowed to make their own plan to achieve the tasks assigned to them. That is, they are allowed to choose autonomously some additional precedence constraints to their assigned tasks. We have to provide the necessary coordination mechanisms to ensure that no conflicts will arise between the resulting plans. The solution we provide is to reduce the temporal constraints of the individual tasks to a set of precedence constraints between tasks and virtual tasks and we solve the resulting coordination problem for tasks with precedence constraints. The solution thus obtained enables us to solve the plan coordination problem with temporal constraints