Nonholonomic Path Planning for Single and Multiple Wheeled Mobile Robots in Environments with Complex Obstacles



  • Background

    This project is on nonholonomic path planning for wheeled mobile robots (WMRs) in environments with complex obstacle distributions. WMR systems are widely being researched for their possible future applications such as autonomous transportation, search and rescure operations in remote areas, mapping of mine deployments and exploration of vast unknown regions of outer space. Much of these applications require development of effective swarm robotics software and hardware. Among many alternative areas currently being researched, planning collision free and efficient paths should have important influence on development of cost-effective swarm systems.


  • Phases of the Project:

    We are currently researching alternative methods utilizing simple and computationally efficient tools for enabling collision free path generation for WMRs. The project objective is to develop computationally efficient single robot planners and use them as agent planners in geometrical formations to synthesize effective flock path planners.

    The first phase of the project is on development of an effective single robot path planner. This phase lasted from mid 2005 to early 2006 and resulted in a computationally efficient yet effective algorithm. The resulting algorithm can achieve improved navigation in typical environments and difficult regions such as ones with U-shaped concave barriers or tunnels. Moreover it can operate effectively with inexpensive hardware such as a small number of ON/OFF sensors and simple microcontrollers. The planner combines a virtual front steering mechanism with an easy to implement obstacle avoidance method generating smooth motion profiles. The utilized reference robot is a bicycle device, the back wheel of which is inherently nonholonomic. Hence as the front axle is steered towards a pre-specified target, the rear axle forms an automatically nonholonomic reference path for a WMR to track. This is an effective method for path planning in obstacle free regions of operating spaces. The obstacle avoidance section of the planner is a simple yet effective algorithm. As the planner is designed to operate with a small number of simple sensors, it cannot form or utilize maps of its surrounding. Hence the obstacles are detected as circular blocks with increasing radius with respect to their impact time. There is also a first order spline based transition period from the avoidance to target steer modes. This transition avoids possible smoothness losses arising from complex obstacle or change of reference robot direction more than acute angles from the target. Moreover lower values of the parameters specifying the transition time causes the planner resembles a wall follower, while high selections enhance planning in concave environments by improving the probability of escaping from the U-gaps or tunnel sections which may cause the WMR to get trapped or reverse its direction. This planner offers the combined advantages of being computationally efficient and easy to implement with simple hardware, in addition to being effective versus most concave and typical convex obstacles. Hence it can be utilized as an agent planner as a part of a swarm planner.

    The second phase of the project is on the collision free collective motion of 20 or more agents in environments of similarly complex obstacle distributions. In this respect the single robot planner of the first phase is used as the agent based planner. To enable collective steering many alternative methods are being applied. The first option is the application of a fixed reference frame (FRF) formation. Co-operation of the single agent planner algorithm and the bounding FRF planners do not require expensive hardware. Hence the resulting flock approach is a viable alternative for flock motion planning of relatively crowded WMR groups. Our technique works effectively for transfer of many robots in obstacle cluttered environments. The efficiency of the FRF based technique can be viewed by simulations.

    The next phase of the project is researching tools which should offer higher collectivity an more even path profiles in environments with complex obstacle distributions and is still in development stage.



  • Some Simulation Results:


Results on Single Robot Planner:

The single agent planner synthesizes smooth paths and reference velocity profiles. Moreover the tracking errors in our simulations were also sufficently low.

A typical sample path in an
environment with convex and
moderately concave obstacles
can be viewed from the link
on the right.

click to view



The simulation path, velocity and error results can be viewed by selecting and clicking the below drop-down list:




Other Results on Single Agent Planner:

A path in an environment
with U-shaped obstacle.
In similar environments
a hyper-ellipse
type virtual obstacle
concept is utilized for
filling the concave gaps
of the obstacles.

click to view



A path plan in a dense tunnel
with many sharp bends

click to view



Results on Collective Path Planning:

The FRF formation based planner improves the collective steering of flocks of 20-30 agents in complex environments. Below Avis are on steering of 20 WMRs (a) by their single robot planners planners Avi4 (b) and by the FRF based formations Avi5.


  • Related Publications:

    • H.T. Sahin, E. Zergeroglu, “Mobile Dynamically Reformable Formations for Efficient Flocking
      Behavior in Complex Environments”, 2008 IEEE International Conference on Robotics and Automation, accepted for publication.

    • H. T. Sahin, E. Zergeroglu, “Computationally Efficient Path Planning for Wheeled Mobile Robots in Obstacle-dense Environments”, Lecture Notes on Control and Information Sciences (LNCIS), Vol. 360, pp: 259–268, 2007. pdf

    • H.T. Sahin, E. Zergeroglu, “A Computationally Efficient Path Planner for a Collection of Wheeled Mobile Robots with Limited Sensing Zones”, 2007 IEEE International Conference on Robotics and Automation, pp: 1074-1079, Italy April 2007. pdf