| Autonomous agents operating in shared, dynamic environments need to coordinate their plans to preclude negative interactions. In this dissertation, we describe an online algorithm that coordinates hierarchical plans. The coordination algorithm incrementally detects potential conflicts action, and recommends temporal ordering constraints to prevent conflicts. By inter-leaving coordination with plan execution, agents can exercise their ability to dynamically select plans in response to runtime contingencies, and do not have to commit to specific courses of action prior to execution. However, merely coordinating plans will not suffice, since coordination commitments can be endangered by plan execution failures caused by exogenous events. Recovering from plan failures at the multiagent system level is the other focus of this work; we describe a failure recovery algorithm that detects plan failure and its ramifications vis-a-vis coordination, and locally repairs the multiagent plan by replacing a failed plan with a substitute plan while working around previously instituted ordering constraints. We report the results of several experiments that evaluate and explain the behavior of the coordination algorithm as a function of various coordination problem parameters, and demonstrate the efficacy of the algorithm by comparing it to alternative coordination strategies. |
