Contributions

The research has been focused on two main threads: the control architecture and the mapping and navigation method. The contributions of the thesis on these two areas are presented next.

Regarding the control architecture, we have proposed a general coordination architecture based on a bidding mechanism. In this architecture there are two types of systems: executive systems and deliberative systems. Executive systems have access to the sensors and actuators of the robot. These systems offer services for using the actuators to the rest of the systems (either executive or deliberative) and also provide information gathered from the sensors. On the other hand, deliberative systems take higher-level decisions and require the services offered by the executive systems in order to carry out the task assigned to the robot. Although we differentiate between these two types of systems, the architecture is not hierarchical, and coordination is made at a single level involving all the systems. This coordination is based on a simple mechanism: bidding. Deliberative systems always bid for the services offered by executive systems, since this is the only way to have their decisions executed. Executive systems that only offer services do not bid. However, those executive systems that require services from any executive system (including themselves) must also bid for them. The systems bid according to the internal expected utility associated to the provisioning of the services. A coordinator receives these bids and decides which service each of the executive systems has to perform.

The bidding mechanism assures that the action actually being executed by the robot is the most valued one at each point in time, and thus, if the systems bid rationally, the dynamics of the bids lead the robot to execute the necessary actions in order to reach a given target. An advantage of using such mechanism is that there is no need to create a hierarchy, such as in the subsumption architecture, but it is dynamically changing depending on the specific situation of the robot and the characteristics of the environment. A second advantage is that its modular view conforms an extensible architecture. To extend this architecture with a new capability we would just have to plug in a new system. Moreover, the coordination mechanism can be applied at different levels of the architecture, be it at the overall architecture level, or within each one of the systems.

For our specific navigation problem, we have instantiated this architecture with three systems: the Pilot, Vision and Navigation systems. The first two being executive systems, and the latter one being deliberative. The Navigation system has been designed as a multiagent system using the same bidding coordination mechanism used in the overall architecture. The high-level task of navigating to a given target has been decomposed into a set of simpler tasks, and we have designed one agent competent in each of these tasks. These agents compete, since they may request the execution of conflicting actions. As in the overall architecture, each agent bids for the services offered by the executive systems, and there is a coordinator agent that decides which is the most urgent request. This request is then sent as the request of the Navigation system, which will have to compete with the requests of the Pilot system.

Regarding the mapping and navigation method, we have addressed two problems: the problem of providing the robot with orientation sense and the problem of building a map of the environment and using it for navigational purposes. Concerning the orientation sense, we have built upon previous work presented by Prescott [55], which describes a model for storing spatial relationships among landmarks in the environment. We have extended Prescott's model so that it can be used with fuzzy information about the locations of landmarks. This is of great importance when working with real robots, as it is impossible to avoid dealing with the imprecision of real world environments. As far as we know, this is the first application of Prescott's model on a real robotic system. As part of this extension, we have also developed methods for building a topological map of the environment, which is used for computing diverting targets, needed by the robot when it finds that the path to the target is blocked.

Although the robotic system proposed in this thesis has been presented as a whole system, including both the control architecture and the mapping method, they are two solutions for two completely independent problems. Thus, we could substitute Prescott's mapping method by any other mapping method (be it another topological approach, a metric approach, etc.). Obviously, the particularities of each system depend on the mapping method (e.g. it would make no sense having a Vision system if the map uses sonar readings), but the overall architecture and its coordination mechanism would not be affected at all by the choice of this mapping method. Similarly, our mapping method could be used in a robotic system controlled by any other architecture (be it hybrid, centralized, etc.).

We have obtained successful results, both on simulation and on real experimentation, showing that the mapping method is capable of building a map of an unknown environment and using 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. Thus, we consider that we have satisfactorily achieved the objective of developing a navigation system with orientation sense for unknown unstructured environments.

In parallel with the experimentation with the real robot, we have also used simulation to apply Machine Learning techniques. More concretely, we have used Reinforcement Learning for having the system learn how to use the camera more appropriately, that is, to use it only when needed. We have also used a Genetic Algorithm approach, in order to tune some of the parameters that define the behavior of the agents in the Navigation system. Successful results have been obtained with both techniques, though there is still much work to do. Actually, they could easily be the subject of several PhD theses, especially the work on Reinforcement Learning.