Page 285 - The Definitive Guide to Building Java Robots

Preston_5564C07.fm Page 266 Monday, September 26, 2005 5:38 AM

266 CHAPTER 7 ■ NAVIGATION

Section Summary

Detecting obstacles can be as sophisticated as your sensors are. I have demonstrated one way
to find them using infrared and sonar, but you could use other methods as your budget allows.
The class created in this section was ObstacleNavigation and it achieved this by constructing a
path around an obstacle.
Currently, the algorithm only works well for a single obstacle, or if you have things temporarily
getting in the way of your robot as it moves. If you think your robot will encounter multiple
obstacles, it may save you time to construct a map with a path where the robot doesn’t have to
deal with more than one object at a time. For that, we’ll have to use a little Graph Theory and
create a software map of our environment.

7.4 Indoor Navigation

Up until now, all our navigation has been in the perfect world of a 100-inch × 100-inch grid.
Rooms in a house or an office do not fit very well in this environment because there are things
like tables, halls, doors, and so on. But as I began to experiment with navigation, I found it
easier to join a few idealized environments together (like the 100 × 100 grid) into a graph than
it was to model an entire room with all its quirks.
For example, using the graph from the introduction, I can create four vertices that each
represent 100 × 100 regions. If I move from A to B, I don’t need to know anything about C and
D. Likewise, if I move from C to D, I don’t need to know anything about A, though I could move
via B if I wanted to take a longer path. (See Figure 7-11.)

Figure 7-11. A room graph

The question is how can I model this in Java? Earlier I created two classes called Vertex
and Edge. I’ll now extend the Vertex class to create an object that models the perfect world on
a 100 × 100 grid. I’ll call this class a region.
A region has four fields. The first is inherited from Vertex and will be so named, while the
second is an int size that gives the distance from the outermost point of the region to its center.
The third is an ArrayList, which stores NavPoints denoting specific locations in the region to