Collaborative Common Path Planning in Large Graphs

This paper studies two-agent path planning algorithms in graphs, where the two agents are assigned independent initial and goal states but are incentivized to share some parts of their travel glued together by scaling down the duet cost function when they move in formation. Applications range from ride sharing to formation flights. After presenting an optimal but unscalable algorithm, we propose a decoupled approach that separates spatial and temporal reasoning by first geometrically finding formation and breaking nodes in the graph then temporally synchronizing the agents on the formation node by adapting their speeds along their paths in the graph. We also introduce an original heuristic function, which accounts for the potential formation paths in the graph and that is used to guide A* search on a cross-product graph representing the coordinated moves of the agents. We finally experiment our framework and compare its variants on grid-like and aircraft formation flight problems.