Robotic Vehicle Competition - Planning

This article follows the previous one about search in our ongoing series about how to design a robotic vehicle capable of navigating on its own through the desert. We are now focused on planning, which drills down to one more level than search does. Planning is sometimes seen as a form of search, and I would tend to agree, but it is a form of search that involves more detail. Whereas with search we were simply concerned with mapping out a generally feasible path from the starting point to the desert destination, with planning we are interested in taking that path and refining it into a series of specific actions that will get the robotic vehicle where it needs to go. Thus, for any car one has a number of specific actions that one can perform, involving various inputs such as the brake, gearshift, clutch, accelerator, and steering wheel. In planning, from an AI point of view, we want to know specifically what we have to do at each step along the way in order to get to our destination - it is not enough to simply have a general route mapped out.

In planning, we ordinarily start with a set of predicates or statements which together describe the state of the world. There is usually a goal state describing the objective that we want to reach and an initial state describing the point that we are starting at. For the robotic planning problem, a typical initial and goal state might look something like the following:
 Diagram - Search

This shows that the robot is initially at a particular latitude and longitude and has as a goal to get to another latitude and longitude (in this case, about 3000 feet to the south). At intermediate points along the way, the robot’s current position and appropriate data might be described using a world state that looks a bit like the following:
 Diagram - Search

A world state will ordinarily consist of a number of predicates showing the current state of the world. In the example above, “At(Robot,33.250N,116.374W)” and “Accelerator(0.5)” are predicates. This particular world state shows the robot half-way from its initial position to its destination, with the accelerator pedal halfway down, the brake and clutch not depressed, moving south (180 degrees) at 25mph in third gear, with the tires and steering wheel not turned.

So it can be seen that a world state, from an AI planning perspective, is something with considerably more information about the current situation than just the positional information that might be addressed in the search phase of the process. In order to successfully navigate through the many different world states available to it, the robot will have at its disposal a number of operators, such as the one shown below:
 Diagram - Search

Each operator will have available to it a number of preconditions. These are predicates that must be true in order for it to be possible to apply the operator. In this case, the operator is to drive south for one minute at 25mph. The preconditions noted above require that the robot be already traveling south at 25mph, with the accelerator halfway down, the brake and clutch not depressed, the tires and the steering wheel not turned, and at a particular latitude and longitude. The operator then also has one or more add conditions and delete conditions. The delete conditions are predicates that were true prior to applying the operator, but cease to be true after the operator was applied. The add conditions are predicates that were not true prior to applying the operator, but become true after the operator is applied. In the case of this particular example, the configuration of the vehicle does not change at all after driving south for one minute, but its latitude will change (by an appropriate amount, measured in degrees, for the speed, time, and direction). This change is noted in the add and delete conditions.

Another example of an operator is shown below:
 Diagram - Search

This operator begins a right turn for the vehicle. It assumes that the vehicle is now traveling in a particular direction in a steady configuration at 25mph, and then initiates a right turn which will leave the tires and steering wheel rotated somewhat, and of course alter the vehicle’s position a little.

We will not attempt to go through all possible operators for the robotic vehicle here. There could be other operators for maintaining a turn, ending a turn, accelerating, braking, changing gears, and so on. The point is that once one has defined all the operators available to the vehicle, the problem of planning can then be addressed in a similar manner to the search problem as described in the last article. The robot needs to search through a large number of possible world states to get from its initial world state to the goal world state. The approaches of heuristic search and island-driven search described in the last article can be adapted to the more complex problem of planning to become heuristic planning and island-driven planning. One would imagine that the route mapped out in the search phase of the solution would be broken down into a number of little pieces, and then the more sophisticated planning approach would be used to decide what particular actions the vehicle needs to take.

Problems that should be addressed by this planning phase that wouldn’t be addressed by the earlier search approach might include the fact that if the robot has to take a sharp turn, the planner could figure out that the only way to do this is to brake sufficiently to allow the turn. Or if the vehicle is going uphill, the planner might be able to determine that it should be in a different gear than if in flat terrain or going downhill. The planner might even have sufficient knowledge of the terrain in different areas of the map to be able to determine that different speeds are appropriate in different parts of the route.

Replanning is also possible if it is determined that the original plan cannot be followed through to completion and must be altered in some way.

Essentially, planning gives you about as much detail as you can get in terms of what the robot is going to do before it actually begins to navigate (and, with replanning, it can enable the robot to change its plan at any time). It gives the robot more detail than with the initial search phase - with planning, the robot should know exactly what speed, what direction, what gear, how fast to turn, and so on throughout the route. Planning, however, cannot help the robot with obstacles that it may encounter on the way that are too small to find on the map, such as trees, rocks, other vehicles, and so on. To avoid these obstacles, it will need computer vision which will be the focus of the next article.

Next article: Computer Vision

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.