Coopération dans les systèmes multi-robots: une contribution au maintien de la connectivité et de l'allocation dynamique des rôles
Lê Văn Tuấn · HAL (Le Centre pour la Communication Scientifique Directe) · 2010
Given the complexity of the tasks to be undertaken by a multi-robot system,the approach most commonly adopted is to “divide and conquer”. It is todecompose the complex task into subtasks, then each of these sub-tasks intosub-sub-tasks. This process is repeated until we reach basic tasks that can bemade by individual robots. This approach, although attractive at first glance, hasthe disadvantage of not always be easy to implement. Indeed, in the majorityof existing work, the decomposition of a complex task into elementary tasks isperformed in a rather ad hoc and dependent upon the target robot system. Thisis indeed a barrier to reuse the result of the decomposition – both software to thelogic level with other robotic systems.In this thesis, we propose a solution that allows any collection of heterogeneousrobots to organize themselves into teams and sub-teams and this, accordingto both the requirements of the task at hand, robots available and resources.Our approach based on the decomposition of a complex task roles, separatesthe concerns of the design and implementation level. Thus, one logical solutionmay be (re)used on multi-robot systems with varying abilities. Once the task isdecomposed into roles, we are facing a well-known, yet unresolved problem :the general problem of assignment of roles to robots effectively. Faced with thisNP-hard problem, we propose heuristics based on the Contract-Net protocol toassign roles to the robots to form coalitions. Each coalition is composed of robotscooperating tightly to perform a single task.Assigning roles to robots, as well as the cooperation of the latter requiresthat the robots must be able to communicate frequently. As a result, the networkconnectivity of robots is a prerequisite for communication. We propose a novelsolution to this problem based on our concept of “connectivity awareness”. It isabout equipping each robot with knowledge of the network structure. We showthat a partial and local knowledge in each robot can be exploited for maintainingnetwork connectivity in the robust distributed manner. Each robot can plan itsown move locally without jeopardizing the overall network connectivity. Indeed,this local knowledge that is the connectivity awareness can be exploited so thateach robot can determine whether the global net