Robot navigation was explored in known, partially known, and unknown environments. Initially, an optimal path was found in a known environment by performing an A* search on a visibility graph that represented the world map. For partially or entirely unknown environments, a D* search was implemented to recalculate the optimal path while the robot was in motion. An evidence grid was used to store information about discovered obstacles.
Our goal for this lab was to design intelligent control software capable of navigating a Nomad mobile robot to a predefined point. This task entails two subtasks: one of determining the best path to the goal, and one of guiding the robot along that path. We explored a number of strategies to achieve the overall goal.
We explored three planning strategies in this lab in increasing order of flexibility and versatility. For our first planner, we were able to specify the locations of all obstacles in the world beforehand, which in turn allowed us to reduce the robot configuration space to an evidence grid (see picture in Extensions section) and search it with the A* algorithm. The second planner permitted us only to 'reveal' the existence and shape of objects to the robot when it came within sonar range, prompting us to employ a grid-based representation of the world (for easy obstacle insertion) and the focussed D* search algorithm for path planning. Finally, the third planner required the robot to construct its own grid-based representation of the world based only on its sonar readings, a representation which D* used to dynamically plot a course through the environment. Of these three planners, the third is the most versatile (it may be used in environments with non-square obstacles or where obstructions are not at all known beforehand).
Our strategies for guiding the robot along its path were fairly straightforward. In each case, the robot was made to 'home in' on a point along the path, choosing a new point whenever it came within a certain distance. This method required the points to be a fair distance away to ensure smooth motion, and while the next point along a visibility graph path almost always far off, paths through a grid-based world representation are not - they always lead through consecutive adjacent nodes. As a solution, the 'next goal point' in these cases was calculated by finding the furthest point ahead in the path that was within the sonars' range. The robot would then 'home in' on that point as it did with the points along the visibility graph path.
The integration of path planning and locomotion was tailored to the amount of worldly knowledge accorded to the robot by each planning strategy. Since the visibility graph planner knew the location of all obstacles beforehand, integration consisted of planning and then letting the robot follow it all the way to the goal. The other two planning strategies had to allow for replanning based on new information. The second planner cycles between homing in on the next distant point along the path and checking and replanning for obstacles. If an unexpected obstacle is detected en route to a point, the locomotion function terminates and forces a planning. The third planner, meanwhile, replans after a set number of robot moves, ensuring that the path is consistent with new information within the evidence grid.
As extensions, we chose to implement some graphical representations of our data to make it
easier to demonstrate. For the first portion of the lab, the implementation of A*, we added a trace
of the complete visibility graph and of the optimal path to make it clear that the algorithm is
finding the optimal path. Interior corners, i.e. those that are formed inside a perpendicular
intersection of two obstacles, were not included in the visibility graph because there is no situation
in which such a node can contribute to the shortest path.
We decided that this feature was so convenient that we permanently integrated it into our code. Now, any set of evidence grids collected during a robot run may be saved sequentially as a series of tiff images. These images can then be converted into an mpeg.
To verify that the robot control software was operating correctly, we subjected each version to repeated simulated test runs in the Nomad robot environment simulator. We also made use of prodigious text and graphical output (e.g. visibility graph plotting, ASCII art graphs of the robot's world representation, TIFF output of evidence grid data) to gain a clear understanding of what the planning software was doing. These combined techniques make us confident that the visibility graph-based planner performs to all expectations. We are equally confident in the capabilities of our other two planners; however, an as-yet unresolved flaw in D* cause both to freeze under certain restrictive conditions.
The one clear conclusion from this lab is that robot control and path planning is not a task to be scoffed at. Large quantities of data are needed to ensure a safe and expeditious traversal of a space, and fast and efficient algorithms like A* and D* are necessary for speedy processing of this data. Since these algorithms and other necessary routines are complex, we recognize that it is important for the code implementing them to be well documented and easy to understand, and we feel that this is an area in which this lab could very much be improved. Overall, we now have an appreciation of the efforts robot researchers go through to create successful robot control systems.