Dijkstra’s on a Robot

Currently I am in an introductory robotics class–and enjoying it immensely.

One interesting challenge was implementing Dijkstra’s algorithm on very limited hardware.

There is no formal graph data structure–this algorithm was implemented as preparation for path planning, and so we produce an extemporaneous graph based on coordinates. Adjacent ‘nodes’ are blocks of 2D space (about the size of the robot). Valid ‘nodes’ can be set and defined by keeping track of a 2D array. This will be useful for obstacle detection later.

The most difficult part was manually implementing many of the functionalities you would desire from the more sophisticated data structures. Several arrays that held the status of nodes were used, and cross-checked against one another.

There were some concessions made–you have to accept a O(|V|^2) run time, for V the set of nodes. Our coordinate space is pretty limited, so this seems an acceptable place to start, and was a fun exercise in simplification.

See the Gist here.

Leave a Reply

Your email address will not be published. Required fields are marked *