LaValle, 2000??) are common in robot programming. Graphically
displaying the output of these algorithms can make them more
accessible to students, and also help programmers find explanations
for unexpected results. Different display techniques can be used
depending on the type of search.
For this project we used the Tekkotsu open source robot programming
framework, available at Tekkotsu.org.. Tekkotsu includes a graphical
user interface for displaying both vision data (as pixel arrays) and
maps, represented as simple geometrical objects (points, lines,
ellipses, polygons, etc.) I extended this tool by adding a new type
of graphical object for efficiently representing complex structures,
such as search trees, composed from the simpler geometric primitives.
I and another student used this tool to display two types of RRT
searches for a mobile robot: one from a navigation path planner, and
one from an arm path planner. The navigation planner output was
displayed as two trees (one grown from the start point and one from
the destination, following the RRT-Connect algorithm). The arm path
planner output was displayed by drawing the different arm
configurations superimposed on the workspace.
I created several demos using RRT searches. In some cases the search
had no solution, and the graphical output helped to illustrate why.
For example, if there were too few iterations or unavoidable
collisions, the trees would never meet. This confirms the
effectiveness of the RRT visualization when explaining the behavior
and unexpected results of the search.