Page 240 - The Definitive Guide to Building Java Robots

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

CHAPTER 7

■ ■ ■

Navigation

Though we travel the world over to find the beautiful, we must carry it with us or we
find it not.

— Ralph Waldo Emerson

7.0 Introduction

Navigation is one of the holy grails of robotics. Of all the challenges in robotics, navigation has
the most applications. If you want a robot that can clean a rug, mop a floor, mow a lawn, or
deliver medicine, all you need is a robot that can navigate.
You will find soon after you begin navigation with your robot that many unforeseen,
unplanned things will happen. They happen because your sensors didn’t interpret the envi-
ronment with the precision you would have liked. I call this poor data or poor interpretation
“noise.” In this chapter, we will start by having the robot navigate within an environment that
has little to zero noise and then increase the environment’s complexity and noise as we go.
Before I begin though, I’d like to introduce a little terminology. The terms come from a
branch of mathematics called Graph Theory.

•A vertex is a synonym for point or node and represents a single element of a set.
•An edge is a connection between vertices.
•A graph is the set of vertices V, and the edges of V.

•A simple graph is an unweighted, undirected graph.
•A directed graph indicates travel between two vertices in a specific direction only.

•A weighted graph is a graph with weights on the edges.
Figure 7-1 shows the different types of graphs.

221