Traditional software design methodologies have been shown to have drawbacks in designing and implementing software systems for robotics. A novel dual-hierarchical object-oriented design methodology is presented, which is well suited to problems of this type. A practical example of the application of this methodology is presented, utilizing CLOS as the implementation vehicle. The methodology developed is shown to facilitate the programming and planning of complex robot tasks, and the provision of generic recovery procedures for exception handling.>

Consideration is given to a world made up of a collection of objects which are all moving with respect to each other. The goal is to design a system capable of reporting predicting all possible object collisions, given that all relevant information is available in due time. Previous approaches are based on the notion of a distance function that reflects the closest distance between objects in the world at any given instant in time. Explicitly including time in the representation makes it possible to obtain an algorithm based on the shortest possible time before the next possible collision. The algorithm deals with all pairwise interactions between objects, sorts the pairs with respect to their predicted collision time, and maintains the most-likely-to-collide pairs at the top of a stack. A novel kind of hierarchy in the representation of the world is thus introduced. To find the shortest possible time before a collision, the trajectory of objects is constrained by imposing bounds on the object's acceleration and velocity. All interacting pairs are classified into buckets that reflect the imminence of the collision. The computing cost is kept constant by reclassifying only one pair from each bucket at each time sample.>