Decentralized multi-robot coordination in crowded workspaces (2015)

The coordination of multi-robot systems is becoming one of the most important areas of research in robotics, mostly because it is required by numerous complex applications. These applications range from intelligent transportation systems, search and rescue robots, and medical robots, to cosmology and astrophysics. The coordination of multi-robot systems is based upon cooperation. The actions performed by each robot take into account the actions executed by the others in such a way that the whole system can operate coherently and efficiently. Regardless of the application, coordination is the key to the successful design and implementation of multi-robot systems. The number of robots involved in the aforementioned applications is increasing along with advances in miniaturization and automation. Consequently, a large number of robots need to share a workspace. This crowded workspace introduces new challenges into the coordination problem by increasing the risk of collision. To take into account communication constraints and sensor ranges, robots rely on local information. Therefore, efficient but simple coordination algorithms are required. This thesis investigates decentralized approaches based on navigation functions for the coordination of multi-robot systems in crowded workspaces. Decentralization allows robots to rely on local information, guarantees scalability and enables real-time deployment. Navigation functions are a special category of potential functions. Their negated gradient vector-field is attractive towards the goal and repulsive with respect to fixed or moving obstacles to avoid collision. In the first part of the thesis, we present the multi-robot coordination problem using navigation functions in a game-theory based framework. We propose a motion model along with a control law that leads the robots to a Nash equilibrium. The existence of the Nash equilibrium enables navigation functions to be exploited for studying, building, and running coordination frameworks for multi-robot systems. In the second part, we address the coordination of autonomous vehicles at intersections. A novel decentralized navigation function is proposed. It guarantees collision-free crossing of autonomous vehicles modeled as first order dynamic systems. The inertia of the vehicles is also introduced in the navigation functions to ensure deadlock-free coordination. The proposed approach does not require adaptation of the road infrastructure and relies upon onboard vehicles sensor data. Compared with traffic lights and roundabouts, the proposed method significantly reduces the travel time and the number of stops, thus decreasing energy consumption and pollution emission. This provides a strong motivation to pursue efforts towards the deployment of autonomous vehicles on roads. In the third part of the thesis, we investigate a coordination framework for a large number of miniaturized fiber positioner robots. The fiber positioner robots are designed and built as parts of the next generation of telescopes enabling large spectroscopic surveys. The proposed decentralized framework ensures the collision-free coordination of the fiber positioners sharing a crowed workspace at the focal plate of the telescope. The dynamical (max speed) and the mechanical (limited actuation range) constraints of the positioners are taken into account in the proposed coordination approach, which significantly reduces the time to reach a new robot configuration.