[A*] I have written a C implementation of the A* algorithm for searching over a graph. It uses a heap-based priority queue and a hashtable (written by Christoper Clark) for data management. It is not optimized but it is easy to understand and good for getting started with search and planning. My implementation allows the user to specify several domain-specific functions for example for computing heuristic values and costs and expanding states. This way, A* can be used on any domain or problem definition without the user having to rewrite the logic for the entire algorithm. (For a turorial on A* and related links visit Justin Heyes-Jones's page.)
[Heap Priority Queue] I have an implementation of a heap-based priority queue (used for the A* implementation). I adapted it for my own use from somebody else's code but I don't know who the original author is. It is implemented in C and very easy to use. (For an introduction to heaps, see the online chapter on heaps and priority queues from Data Structures and Algorithms with Object-Oriented Design Patterns in C++ by Bruno R. Preiss. You can download a tarball of this code. It containts documentation and a simple example of usage. FYI: save it into its own directory before untarring. Contents: HeapPQ.c, HeapPQ.h, exampleHeapPQ.c, and html documentation.
[PurePursuit] I have written a C++ implementation of the pure-pursuit algorithm used for path following in non-holonomic vehicles. From Implementation of the Pure Pursuit Path Tracking Algorithm by R. Craig Coulter, #CMU-TR-RI-92-01 published in January 1992:
What is pure pursuit? "Pure pursuit is a tracking algorithm that works by calculating the curvature that will move a vehicle from its current position to some goal position. The whole point of the algorithm is to choose a goal position that is some distance ahead of the vehicle on the path. The name pure pursuit comes from the analogy that we use to describe the method. We tend to think of the vehicle as chasing a point on the path some distance ahead of it - it is pursuing that moving point. That analogy is often used to compare this method to the way humans drive. We tend to look some distance in front of the car and head toward that spot. This lookahead distance changes as we drive to reflect the twist of the road and vision occlusions."
What does the algorithm do? "The pure pursuit approach is a method of geometrically determining the curvature that will drive the vehicle to a chosen path point, termed the goal point. This goal point is a point on the path that is one lookahead disrunce from the current vehicle position. An arc that joins the current point and the goal point is constructed. The chord length of this arc is the lookahead distance, and acts as the third constraint in determining a unique arc that joins the two points. Consider the lookahead distance to be analogous to the distance to a spot in front of a car that a human driver might look toward to track the roadway."
[OpenGL Skeleton] I've written skeleton code in C++ for creating an OpenGL window, drawing, panning up and down, left and right, and zooming in and out. Its quite easy to use and customize and good if you want a quick visualization for your research. However, I haven't had time to document it. You can download a tarball of this code. It containts a simple example of usage.
[OpenGL Drawing Utility] I find myself using the same chunks of OpenGL code over and over again, e.g. to render a set of points defined in a 2D array, to draw boxes, to draw pie shapes. It also contains functions to draw pioneer robots or outdoor vehicles (very simple looking but they get the job done). I've bundled these all up into a single library called libdrawmisc. Its pretty obvious how to use it.
[Various Code Fragments]
[Gaviotas] I recently gave a presentation on Gaviotas to the Technology and Development for 4 Billion course taught by Bernardine Dias and Rahul Tongia. My presentation is based on Alan Weisman's book Gaviotas: A Village to Reinvent the World and on information/pictures from Friends of Gaviotas. I introduced the class to Gaviotas as a community and as a research center and also talked about my own interest in doing a research project on/with Gaviotas. PPT (1.4MB), HTML
[Multirobot Teams] I am TA-ing CMRobobits (15-491) this semester (Fall 2004) with Sonia Chernova. The course is taught by Manuela Veloso and Paul Rybski and it intended to be an introduction to robots via robot "bits" (i.e. vision, motion, localization). I gave the first lecture on multi-robot coordination, focusing specifically on market-based techniques and going on to the taxonomy of approaches. PPT (1.6MB), HTML