A multi-agent approach to qualitative navigation in robotics

Abstract

La navegació en entorns desconeguts no estructurats és encara un problema obert en el camp de la robòtica. En aquesta tesi presentem una aproximació per a la navegació de robots basada en la combinació de navegació basada en landmarks, representació fuzzy d'angles i distàncies i una coordinació multiagent basada en un mecanisme de dites. L'objectiu de la tesi ha sigut desenvolupar un sistema de navegació robust amb sentit de l'orientació per a entorns no estructurats usant informació visual.<br/><br/>Per tal d'assolir aquest objectiu, hem centrat els nostres esforços en dues línies d'investigació: mètodes de navegació i construcció de mapes, i arquitectures de control per a robots autònoms.<br/><br/>Pel que fa als mètodes de navegació i construcció de mapes, hem extès el treball presentat per Prescott per tal que es pugui utilitzar amb informació fuzzy sobre la localitazció dels landmarks. A part d'aquesta extensió, tambés hem desenvolupat mètodes per a calcular objectius alternatius, necessaris quan el robot troba el camí bloquejat.<br/><br/>Pel que fa a l'arquitectura de control, hem proposat una arquitectura general que utilitza un mecanisme de dites per a coordinar un grup de sistemes que controlen el robot. Aquest mecanisme pot ser usat en diferents nivells de l'arquitectura. En el nostre cas l'hem usat per a coordinar els tres sistemes del robot (Navegació, Pilot i Visió), i tambés per a coordinar els agents que composen el sistema de Navegació. Usant aquest mecanisme de dites, l'acció que executa el robot és la més ben valorada en cada instant. D'aquesta manera, i si els agents fan les dites d'una manera racional, la dinàmica de les dites porta el robot a executar les accions necessàries per tal d'arribar a l'objectiu indicat. L'avantatge d'utilitzar aquest mecanisme és que no cal imposar una jerarquia entre els sistemes, com passa en l'arquitectura de subsumpció, si no que aquesta jerarquia canvia dinàmicament, depenent de la situació en què es troba el robot i les característiques de l'entorn.<br/><br/>Hem obtingut resultats satisfactoris, tant en simulació com en experimentació amb un robot real, que confirmen que el sistema de navegació és capaç de construir un mapa d'un entorn desconegut i utlitzar-lo per a moure el robot d'una posició inicial a un objectiu donat. L'experimentació tambés ha mostrat que el sistema de coordinació basat en dites que hem dissenyat produeix el comportament global d'executar les accions necessàries en cada instant per tal d'arribar a l'objectiu.

Navigation in unknown unstructured environments is still a difficult open problem in the field of robotics. In this PhD thesis we present a novel approach for robot navigation based on the combination of landmark-based navigation, fuzzy distances and angles representation and multiagent coordination based on a bidding mechanism. The objective has been to have a robust navigation system with orientation sense for unstructured environments using visual information.<br/><br/>To achieve such objective we have focused our efforts on two main threads: navigation and mapping methods, and control architectures for autonomous robots.<br/><br/>Regarding the navigation and mapping task, we have extended the work presented by Prescott, so that it can be used with fuzzy information about the locations of landmarks in the environment. Together with this extension, we have also developed methods to compute diverting targets, needed by the robot when it gets blocked.<br/><br/>Regarding the control architecture, we have proposed a general architecture that uses a bidding mechanism to coordinate a group of systems that control the robot. This mechanism can be used at different levels of the control architecture. In our case, we have used it to coordinate the three systems of the robot (Navigation, Pilot and Vision systems) and also to coordinate the agents that compose the Navigation system itself. Using this bidding mechanism the action actually being executed by the robot is the most valued one at each point in time, so, given that the agents bid rationally, the dynamics of the biddings would lead the robot to execute the necessary actions in order to reach a given target. The advantage of using such mechanism is that there is no need to create a hierarchy, such in the subsumption architecture, but it is dynamically changing depending on the specific situation of the robot and the characteristics of the environment.<br/><br/>We have obtained successful results, both on simulation and on real experimentation, showing that the mapping system is capable of building a map of an unknown environment and use this information to move the robot from a starting point to a given target. The experimentation also showed that the bidding mechanism we designed for controlling the robot produces the overall behavior of executing the proper action at each moment in order to reach the target.