We address the problem of optimal coordinated motions of multiple agents moving in the same planar region. The agents' motions must satisfy a separation constraint throughout the encounter to be conflict-free. The objective is to determine the conflict-free maneuvers (motions) with the least combined energy, while taking into account the fact that agents may have different priorities. A formal classification of conflict-free maneuvers into homotopy types is introduced by using their braid representation. Various local and global optimality conditions are derived through variational analysis in the presence of the separation constraint. In the case of two agents, these optimality conditions allow us to construct the optimal maneuvers geometrically. For the general multi-agent case, a convex optimization algorithm is proposed to compute within each homotopy type a solution to the optimization problem restricted to the class of multilegged maneuvers. Since the number of types grows explosively with the number of agents, a stochastic algorithm is suggested as the "type chooser," thus leading to a randomized optimization algorithm.