Routing-based navigation of dense mobile robots

In the future, many teams of robots will navigate in home or office environments, similar to dense crowds operating currently in different scenarios. The paper aims to route a large number of robots so as to avoid build-up of congestions, similar to the problem of route planning of traffic systems. In this paper, first probabilistic roadmap approach is used to get a roadmap for online motion planning of robots. A graph search-based technique is used for motion planning. In the literature, typically the search algorithms consider only the static obstacles during this stage, which results in too many robots being scheduled on popular/shorter routes. The algorithm used here therefore penalizes roadmap edges that lie in regions with large robot densities so as to judiciously route the robots. This planning is done continuously to adapt the path to changing robotic densities. The search returns a deliberative trajectory to act as a guide for the navigation of the robot. A point at a distant of the deliberative path becomes the immediate goal of the reactive system. A ‘centre of area’-based reactive navigation technique is used to reactively avoid robots and other dynamic obstacles. In order to avoid two robots blocking each other and causing a deadlock, a deadlock avoidance scheme is designed that detects deadlocks, makes the robots wait for a random time and then allows them to make a few random steps. Experimental results show efficient navigation of a large number of robots. Further, routing results in effectively managing the robot densities so as to enable an efficient navigation.