Robotic Vehicle Competition - Search

This is the next in a series of articles regarding how a robotic vehicle - controlled entirely by AI without human intervention - would successfully navigate a course through the Mojave desert. This article is on search. In reading this article, it is important to understand that search is something the robot does before it actually starts physically moving. This should be kept in mind - so when we discuss, for example, the robot exploring a particular path, it is important to understand that this is something that it isn’t doing physically but is doing in its memory before it starts to drive - or, alternatively, the robot might be searching the later parts of the course while physically driving the early part. Later articles will focus on the parts of the system that would support the actual driving.

Most AI systems perform search in one form or another. From the point of view of an AI system, search is a little different from the kind of search that one does on Google or in a file or a hard drive, although the concepts are at least a little similar. From the point of view of AI, search is a very computer-intensive process of finding the best solution to a particular problem by exhaustively looking through as many alternative solutions as possible. The available solutions may not be immediately obvious in looking at the problem and usually tend to grow in quantity and/or size exponentially as the problem gets bigger. Usually the search algorithm combines a combination of brute force computing power - using the ability of the computer to search billions of possibilities a second - with some intelligent means for controlling the search.

Probably the best example of search where a certain amount of AI is involved - albeit not that advanced - that the average person comes across is when they go to Yahoo! for driving directions. There are many thousands or millions of routes from point A to point B and Yahoo! usually (albeit not always) comes reasonably close to providing the most efficient route for a given trip. This isn’t necessarily easy to do.

Since we are on the topic of driving, let’s return to the original problem that is motivating these articles: programming a robot to automatically drive through the Mojave desert. Before the robot can deal with the lower level details of avoiding small surface obstacles in the desert, it has to first map out a high level route from getting from its origin to its destination. Let’s imagine that the robot driver is given its origin, its destination, and some kind of contour map (in electronic form, of course) of the desert. Let’s also assume that it has some form of GPS tracking system so that it knows its general position at all times. The robot may then set as its general goal the task of getting from the origin to the destination while charting as flat a course as possible (avoid changes in elevation) through the desert.

This is shown in the picture below where the robot is attempting to navigate from the green circle to the red circle, but faces a large hill in the middle. If the robot vehicle follows a path along the yellow arrows then the robot avoids having to climb up an insurmountable hill. This is common sense for a human but not necessarily easy to do in an automated fashion.
 Diagram - Search

The simplest way of doing this would be to simply map out all possible routes (in short steps) through the desert on the map and find the best one. The problem with this is that there are likely to be far too many possible routes to compute. So the robot needs some way of minimizing the number of routes that are explored. Being a computer, the robot can examine a great many possible routes - but not an infinite number.

The two most general approaches are referred to as breadth-first search and depth-first search. In both possible kinds of search, the possible paths from the starting point to the destination are represented in a tree structure. With breadth-first search, the robot would first examine all paths to the destination that can be done in one step, then all paths to the destination that can be done in two steps, and so on, until it finds a route to the destination. (Actually it would first need to define what a “step” is for a robot that is a car traveling offroad - perhaps it could be defined as moving the car one car length in a compass cardinal direction.) This approach will guarantee that it finds the shortest possible path to the destination, but since the number of steps is going to be large for a trip through the desert, the number of possible paths it will have to examine in order to find that shortest path is going to be astronomical, and well beyond the capabilities of even the most advanced supercomputer (of today, at any rate). So breadth-first search won’t work for navigating through the desert, although it might work better for a robot mapping out shorter trips - for example a household robot trying to figure out how to vacuum across the living room without running into the furniture.

An alternative approach to search is depth-first search, where the robot, once it starts mapping out a route, always explores that route completely until it gets to its goal (in this case a destination). This actually might work fairly well for the desert robot if there is a fairly simple path to the destination and the obstacles are not too maze-like. The problem is that if the robot makes a wrong turn (electronically while examining the map) and has to retrace its steps, it is going to follow that same inefficient route while actually driving the route. So depth-first search is likely to be a bit better for this type of problem, but is still not going to be ideal (and, at worst, the robot will get trapped and end up going in circles).

Another approach that is more likely to succeed with navigating through the desert is heuristic search. In heuristic search, the robot has some form of heuristic for determining how good a potential partial path through the desert is. A simple heuristic would tell the robot to favor paths that get the robot closer to the goal and result in having to traverse only gentle inclines up or down. A more sophisticated heuristic might have the robot examine the map in its immediate vicinity and avoid directions that appear to result in it getting trapped (surrounded by hills or canyons, for example) or even getting too close to hills (on the theory that the terrain is likely to be more rocky the closer one gets to a hill). Furthermore, while examining possible paths, the robot would keep track of a number of good paths (according to its heuristic) - perhaps examining the best several thousand paths according to its heuristic. In this way it combines a certain level of intelligence (the heuristic that enables it to determine what a promising path is) with the raw computing power of being able to examine a great many possibilities. The robot would keep track of, let us say, the best ten thousand paths that it has seen so far, adding additional possible paths as it comes to a fork in the road, and discarding paths that are no longer seen as competitive.

Island-driven search is another approach that the robot could take. With island driven search, the robot divides the problem into two pieces by first looking for a suitable point about midway between the start and destination. In the case of this problem, a suitable point would be one whose elevation is not too different from the origin or destination, and is not too far from the midpoint. After it has thus subdivided the route, it plans to travel first from the origin to the island, and then from the island to the destination. So now it has two search problems: getting from the origin to the island, and getting from the island to the destination. By continually dividing the problem into pieces like this, the robot will eventually reduce it to “baby steps” that are small enough to be undertaken without search. Island-driven search is likely to be especially effective in mapping out routes through established streets, as for example with Yahoo!’s driving directions, because the algorithm can be given certain pre-established “islands” like major thoroughfares or intersections to guide its search.

The robots in the desert race, like the winner Stanley, probably used some combination of heuristic search and island-driven search to complete their task, as likely does Yahoo!’s driving directions. In the case of the robots, there was probably also a lot of very specific and ad hoc programming relating to the particular terrain the robot was to navigate to ensure optimal performance in a competitive environment. Because of the fact that it was a race, the robots may have interleaved the compute-intensive search process with actual driving, beginning driving the early parts of the route while continuing to apply considerable computational power to searching for the best route through the remainder of the course. The robots probably didn’t wait a long time at the starting line computing in a complex search algorithm since that would have put them at a competitive disadvantage - more likely search and driving largely happened at the same time.

In the next article we will look at planning. Planning is similar to search but a bit more sophisticated. With search, we just mapped out a route through the desert. With a plan, more detail would be provided such as what speed to drive at, what gear to use, when to turn, how fast to turn, and so on - steps that are necessary in actual driving.

Next article: Planning


Home: Ramalila.NET



All copyrights are maintained by respective contributors and may not be reused without permission. Graphics and scripts may not be directly linked to. Site assets copyright © 2000 RamaLila.com and respective authors.
By using this site, you agree to relinquish all liabilities and claims financial or otherwise against RamaLila and its contributors. Visit this site at your own risk.