Traditional robot motion planning and obstacle avoidance concentrated on determining a path in the presence of holonomic or integrable, equality and inequality constraints on the configuration space. Some solutions to this problem include graph search procedures given the map of the world, path planning using artificial potential functions and behavior and motor schema based reactive planning systems. In practice however most robotic systems include constraints that are not holonomic. Such kinematic constraints cannot be integrated to give constraints which are explicit functions of position variables, (e.g. a front wheel drive car, dextrous manipulation or assembly with robotics hands). It has been shown that these systems are controllable regardless of the structure of nonholonomic constraints and analytical tools based on Lie algebras to generate control sequences to steer these systems have been proposed. Brockett showed that these systems cannot be stabilized via smooth time invariant state feedback. This led to the design of piecewise smooth feedback controllers, time-varying periodic controllers and explicit control design to generate time-varying stabilizable control laws.
As most of the above research on steering and stabilization of nonholonomic systems assumes an obstacle-free world, the problem of autonomous path planning and obstacle avoidance with nonholonomic robots becomes a nontrivial one. Traditional planners assume that arbitrary motion is permitted, and hence they cannot be applied to nonholonomic robots as they result in nonfeasible paths, i.e. trajectories that do not satisfy the constraints on the configuration variables. This motivates the need for a hybrid control strategy and in our work we present a path planner to solve the problem of real-time obstacle avoidance and path planning with nonholonomic robots.
Unlike earlier approaches the planner integrates features of reactive planning systems with modern control theory approaches to steer and stabilize nonholonomic robots. Planning is restricted to the two dimensional domain. The planner assumes that the robot has limited range sensors and knowledge of the coordinates of the goal and its own coordinates at any instant of time. No restrictions are placed on the size and shape of the obstacles. As a first step towards the design of the planner we introduce a formal language for motion planning in which we model the robot as a kinetic state machine. The language enables us to define and reinterpret some of the existing notions of ``behaviors'', ``plans'' etc. We then introduce a hybrid control strategy that is motivated by the hierarchical and distributed nature of neuromuscular control. Planning is done at two levels - global and local. For local planning obstacle-free (non)feasible paths are generated using potential functions assuming that the robot is holonomic. A feasible path is then generated that obeys the constraints in the configuration variables. As feasible trajectories are only approximation to the trajectories generated using potential functions collision with obstacles while tracing the feasible trajectory is avoided by encoding sensor information in the kinetic sate machine. In addition this information is also present in a lower level feedback loop while the robot is in motion. At a global level heuristics along with the world map generated while the robot is {\em en \. route} to the goal are used to solve the problem of periodic orbits encountered by using potential functions and also to improve the ``performance'' of the planner in situations where the same of similar tasks may have to be repeated.
At present we have a simulation of some aspects of the above suggested control strategy with disjoint obstacles on a Silicon Graphics Workstation. For the purposes of simulation, the robot is assumed to have a rectangular base with a front-wheel drive and free-wheeling castors that provide stability at the rear end. Each of the front wheels can be individually controlled resulting in three kinds of motion - translation, rotation and translation with rotation. Infrared sensors with limited range are used for object detection. The control strategy generates piecewise smooth trajectories avoiding cycles.
It is probably for the first time that the techniques of nonholonomic motion planning and reactive planning systems have been integrated. Further the motion description language and suggested architecture provides a general framework to carry out such integration. Our approach combines algorithm development on a realistic simulator with experimentation on robots R2 (Itchy) and T2 (Scratchy).
We plan to explore the possibilities of using adaptive neural nets to generate intelligent behaviors for path planning with moving obstacles. In addition we plan to increase the levels of parallelism in the control strategy for more efficient real time planning. We hope to include error recovery strategies in our future work.