Abstract
The optimal multi-agent coordination problem tries to find the motions for a group of agents that start from a set of initial positions and end at a set of destination positions with the least energy expenditure. Often times, the problem is formulated with constraints on the formation of the agents, namely, distances between certain pairs of agents need to be kept constant throughout the process. In this paper, the optimal multi-agent coordination problem is studied for the special case when the graph describing the formation constraint is a tree. The equations characterizing the optimal coordinated motions are derived in a suitably chosen coordinate system. The solutions to these equations, however, may fail to be optimal once extended beyond certain points called the conjugate points due to the failure of second order optimality condition. Two methods for computing the conjugate points are introduced. For an instance of the problem where the agents try to rotate around a center point, the conjugate points along a natural candidate solution are characterized analytically and verified through numerical simulations. Moreover, better solutions are found that consume less energy than the candidate solution after it is extended beyond its first conjugate point.
Date of this Version
May 2007