Multiagent Navigation System Simulation

The goal of simulation was to check whether our approach, that is, the architecture, the bidding coordination mechanism and the mapping method, could lead to a robust navigation system.

We implemented the agents of the Navigation system and tested the algorithm on the Webots simulator and in our own developed one. Each agent was executed as an independent thread, and they used shared memory for message passing. We also simulated the Pilot and Vision systems on both simulators. We set the parameters of each of the agents by hand. We first set their values intuitively, and slightly modified them after some simulation trials.

As a first step, we checked whether the bidding mechanism was able to adequately coordinate the agents of the Navigation system and the Pilot, so that the task of reaching the target was accomplished. The Pilot system used was not able to inform about the presence of long obstacles between landmarks, although it would avoid them. For this reason, we were not still checking the mapping and navigation capabilities of the system.

Figure 5.1 shows a navigation run in the Webots simulator. It shows the path followed by the robot from a starting point to a target landmark. The environment was composed by a set of landmarks (shown as circles), a river (the thick blue traversing line) with a couple of bridges, and some fences and other obstacles. These obstacles did not occlude the target landmark, so it was visible from any location of the environment. The task to be performed was to reach the target (at the left-hand side of the world) avoiding any obstacle encountered on the way.

Figure 5.1: Robot's path from starting point to the target

At the very beginning, the distance to the target is unknown, so the Distance Estimator agent (DE) bids very high to move the robot orthogonally to the line connecting it to the target and looking to the target, so that the Map Manager can estimate the distance to the target. The Target Tracker agent (TT) bids for moving and looking towards the target, but the bids of DE are higher and the robot moves orthogonally. As the robot moves, the Map Manager computes the distance to the target, and the imprecision computed by the DE decreases, causing its bids also to decay. At a given point, the bids of TT are higher than those of DE, and the robot starts going towards the target. Since there are no obstacles around, the Pilot does not bid at all. However, after some advance, the robot encounters an obstacle, and the Pilot bids very high to avoid it, surpassing the bids of TT and DE. When the obstacle has been totally avoided, the Pilot stops bidding, the bids of TT win again, and the robot moves towards the target. This situation is repeated a couple of times until the robot finally reaches the target.

Although the environment used in this first step was simple, mainly because of the constant visibility of the target, simulations showed that the bidding coordination mechanism worked properly, since it was able to coordinate the different agents and the Pilot.

Figure 5.2: Computing diverting targets

Figure 5.3: Associated map

The next step was to test the mapping and navigation capabilities of the Navigation system. In this step we used our own developed simulator, with a better Pilot system, capable of informing about the linear obstacles between landmarks, and with more realistic environments including occluding obstacles, so that the target was not visible all the time.

In Figure 5.2 we see how the Navigation system computes diverting targets for reaching the initial target when this is lost. In this environment, filled polygons are occluding obstacles, and empty ones are non-occluding ones, thus, permitting the visibility of the target from the starting point. At point A, it sees the target and starts going towards it. However, at point B, it detects an obstacle, so the Pilot forces the robot to turn. When it reaches point C, it cannot see the target anymore, as it is behind an occluding obstacle. At this point, a diverting target is computed (in this case, landmark 30 is selected). The robot starts going to this diverting target. Once reached (point D), a new diverting target is computed (landmark 38 is selected), and the robot goes toward it. At point E, after reaching the current diverting target, a new one is computed (landmark 12), which is reached at point F. From this point, it sees the initial target again, goes straight towards it, and finally reaches the target.

Someone may ask why the Navigation system computed so many diverting targets, instead of trying to go towards the initial target more frequently. The reason was that the risk was too high very often. This was because of the narrow view field of the camera and the fact that the system was not using Visual Memory, thus, having too few landmarks in sight very often. Although the performance was good enough - the robot reached the target - this behavior of constantly computing diverting targets was not what we really wanted. Moreover, in the situation of the robot being in an area with very few landmarks, possibly seeing only the target, the risk would be very high, but it would not be a wise decision to stop going towards the target and, instead, compute a diverting target. That is why the Rescuer agent was modified so that it did not take into account the risk, as presented in the previous chapter.

In Figure 5.3 the map generated while reaching the target is shown. Although internally the Map Manager agent stores the map as a graph, here, for clarity, we show the triangular regions corresponding to the nodes of this graph. As can be seen, the map has many overlapping regions, unconnected regions and regions with obstacles inside. Obviously, it is not a very good representation of the environment. In order to obtain a better map of the environment, we modified the mapping algorithm so that it included the constraints presented in Chapter 3. As will be seen in the experimentation with the real robot (Chapter 6), the modified mapping algorithm obtains much better maps.

Although in the simulation we simplified the task in comparison to navigating through a real environment (the Vision system worked perfectly, without any limitation on its view range, the Pilot used sonars for obstacle avoidance), the results obtained, showing that the coordination and mapping worked well, were very promising and encouraged us to keep working on the refinement of the system in order to test it on the real robot. However, even though the main experimentation was to be done with the real robot, we still employed simulation to apply Machine Learning techniques in order to automatically tune the parameters and obtain better performance. In the following sections we describe how we have applied these techniques.