Logical Architecture for Robot Path Planning

Abstract

In this work we present a robot path planning architecture based on Lee's routing algorithm. This algorithm was originally conceived to obtain minimal conductor nets among terminals on VLSI circuits. In our system it provides a simple and robust mechanism to compute near to shortest free paths in two-dimensional configuration environments. We incorporate this algorithm in a planning system, and the resulting architecture can be used to generate trajectories in order to guide a mobile agent from an initial point to a final (static or moving) position of the working space, avoiding not only static but also moving obstacles. The guidance engine is implemented as a rule-based version of Lee's algorithm, embedded in a multi-paradigm software system that performs logical inferences in a Prolog component, whose results are provided to an imperative and numerical processing compiled component. This allows a neat factorization of the functionality of the system: high level representation of the navigation algorithm is implemented through its logical formulation, and easy and natural means to acquire the layout of the environment with computer vision and image processing techniques is implemented via numerical programming. The same imperative approach is also natural to provide 2D or 3D visualization and simulation features to aid to understand the ongoing process. Thus, our architecture features both the speed and versatility of a visual language application, and the abstraction level and modularity of a logical description.