Algorithms For Dummies

  Considering Heuristics 

     375

 

»

Occupancy grid maps: These maps divide the surroundings into small, empty 

squares or hexagons, filling them in when the robot’s sensors find an obstacle 

on the spot they represent. You can see an example of such a map at the Czech 

Technical University in Prague: 

http://cmp.felk.cvut.cz/cmp/demos/Omni/ 

mobil/

. In addition, check out the videos showing how a robot builds and 

visualizes such a map at 

https://www.youtube.com/watch?v=zjl7NmutMIc

 

and 

https://www.youtube.com/watch?v=RhPlzIyTT58

.

You can visualize both topological and occupancy grid maps as graphic diagrams. 

However, they’re best understood by algorithms when rendered into an appropri-

ate data structure. The best data structure for this purpose is the graph because 

vertexes  can  easily  represent  squares,  hexagons,  landmarks,  and  waypoints. 

Edges can connect vertexes in the same way that road, passages, and paths do.

Your  GPS  navigation  device  operates  using  graphs.  Underlying  the  continuous, 

detailed, colorful map that the device displays on screen, road maps are elaborated 

behind the scenes as sets of vertexes and edges traversed by algorithms helping 

you find the way while avoiding traffic jams.

Representing the robot’s territory as a graph re-introduces problems discussed in 

Chapter 9, which examines how to travel from one vertex to another using the 

shortest path. The shortest path can be the path that touches the fewest vertexes 

or the path that costs less (given the sum of the cost of the crossed edge weights, 

which may represent the length of the edge or some other cost). As when driving 

your car, you decide not only on the distance driven to reach your destination but 

also on traffic (roads crowded with traffic or blocked by traffic jams), road condi-

tions, and speed limits that may influence the quality of your journey.

When finding the shortest path to a destination in a graph, the simplest and most 

basic algorithms in graph theory are depth-first search and Dijkstra’s algorithm 

(described in Chapter 9). Depth-first search explores the graph by going as far as 

possible from the start and then retracing its steps to explore other paths until it 

finds  the  destination.  Dijkstra’s  algorithm  explores  the  graph  in  a  smart  and 

greedy  way,  considering  only  the  shortest  paths.  Despite  their  simplicity,  both 

algorithms are extremely effective when evaluating a simple graph, as in a bird’s- 

eye view, with complete knowledge of the directions you must take to reach the 

destination and little cost in evaluating the various possible paths.

The  situation  with  a  robot  is  slightly  different  because  it  can’t  perceive  all  the 

possible  paths  at  one  time,  being  limited  in  both  visibility  and  range  of  sight 

(obstacles may hide the path or the target may be too far). A robot discovers its 

environment as it moves and, at best, can assess the distance and direction of its 

final destination. It’s like solving a maze, though not as when playing in a puzzle 

maze but more akin to immersion in a hedge maze, where you can feel the direc-

tion you are taking or you can spot the destination in the distance.

---

376