Reactive Navigation of Multiple Moving Agents by Collaborative Resolution of Conflicts

K. Madhava Krishna    Henry Hexmoor    Srinivas Chellappa   

IIIT Hyderabad, India    CSCE DepartmentUniversity of ArkansasFayetteville, Arkansas    CS DepartmentCarnegie Mellon UniversityPittsburgh, Pennsylvania   


In navigation that involves several moving agents or robots that are not in possession of each other’s plans, a scheme for resolution of collision conflicts between them becomes mandatory. Aresolution scheme is proposed in this paper specifically for the case whereit is not feasible to have a priori the plans and locations of all other robots, robots can broadcast information between one another only within a specified communication dis-tance, and a robot is restricted in its ability to react to collision conflicts that occur outsideof a specified time interval called the reaction time interval. Collision conflicts are re-solved through velocity control by a search operation in the robot’s velocity space The existence of a cooperative phase in conflict resolution is indicated by a failure of the search operation to find velocities in the individual velocity space of the respective robots in-volved in the conflict. A scheme for cooperative resolution of conflicts is modeled as asearch in the joint velocity space of the robots involved in conflict when the search in the individual space yields a failure. The scheme for cooperative resolution may further in-volve modifying the states of robots not involved in any conflict. This phenomenon ischaracterized as the propagation phase where cooperation spreads to robots not directly involved in the conflict.Apart from presenting the methodology for the resolution of con-flicts at various levels (individual, cooperative, and propagation), the paper also formally establishes the existence of the cooperative phase during real-time navigation of multiple mobile robots. The effect of varying robot parameters on the cooperative phase is pre-sented and the increase in requirement for cooperation with the scaling up of the numberofrobotsinasystemisalsoillustrated. Simulation results involving several mobile robots are presented to indicate the efficacy of the proposed strategy.