Space Partition for Conflict Resolution of Intersecting Flows of Mobile Agents

This paper studies the conflict resolution for intersecting flows of mobile agents based on planar space partition. The idea of space partition is first demonstrated for two intersecting flows of mobile agents. Then, for three intersecting flows, where simple decentralized conflict avoidance rules may not handle all traffic scenarios, it is proved that certain periodic partitions of space are able to provide conflict resolution for any distribution of agents in the flows. A computational procedure based on mixed integer programming is further proposed to find optimal space partitions. The approach of space partition is not an online optimization algorithm. An online algorithm may find optimal resolution of conflict for a specific set of mobile agents but has to be rerun each time when new agents arrive, whereas a periodic partition of space provides a priori geometrical configuration for conflict avoidance regardless of the number and arriving patterns of the agents. Moreover, the offline nature of space partition does not imply a decrease of performance. As demonstrated in an example involving three symmetrically arranged agent flows, the optimal space partition has found a tight upper bound for the magnitude of any conflict-free maneuvers.