Interleaved plan coordination and execution in dynamic multi-agent domains

Coordinating agents need to anticipate how their individual actions will affect each other. Many proposed algorithms have taken to searching through the joint plan space to find compatible action sequences before execution is begun. In dynamic environments, “reactive” strategies have been employed, where agents can wait until they must act to decide on their actions. However, waiting to decide on actions confounds coordination, since an action locally selected by an agent now might be incompatible with actions that others are taking or with actions that it or other agents might later discover they need to take. Proposed solutions include incremental merging of short term plans, institution of social laws, and exchanging post facto updates about agents´ decisions on the fly and letting coordination trail behind. Since these approaches have either focused on generating a single solution or pruning certain plan combinations from the solution space, they are not particularly suited to agents which might have to select from several alternative plans to achieve their tasks, since the approaches rule out options in the solution space prior to execution. We propose an algorithm that coordinates agents with hierarchical task networks by using a least commitment strategy to incrementally construct a multi-agent plan at runtime