Electrostatic Methods for Perfect Matching and Safe Path Planning
Nak-seung Patrick Hyun, Yuval Peres · 2018
In this paper, a new perfect matching algorithm for two sets of agents of the same sizes is proposed by simply following the electrostatic fields (ESF) in higher dimensional space. The algorithm also generates trajectories for each agent to avoid collisions between the same types. The proposed ESF follows the gradient descent of the harmonic potential function. It is shown that there are no saddle points, but there exists an invariant manifold which may evolve all agents to some consensus point. However, this invariant manifold (IM) is measure zero in the state space, and a sufficient condition for IM being unstable is proposed. Inspired by electrostatic forces with nonuniform charges, a weighted electrostatic field is proposed by following the gradient descent of a subharmonic function. Similarly, safe trajectories are generated with perfect matching, but the final assignment may be different from the original ESF method. A simulation result for the performance of the matching (an average L2distance among the matching) is shown at the end and compared with the optimal (Hungarian) method.