Nonholonomic Path Planning for Single and Multiple Wheeled Mobile
Robots in Environments with Complex Obstacles
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
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.
Results on Single Robot Planner:
agent planner synthesizes smooth paths and reference velocity
profiles. Moreover the tracking errors in our simulations were
also sufficently low.
typical sample path in an
environment with convex and
moderately concave obstacles
can be viewed from the link
on the right.
The simulation path, velocity and error results can be
viewed by selecting and clicking the below drop-down list:
Other Results on Single
in an environment
with U-shaped obstacle.
In similar environments
type virtual obstacle
concept is utilized for
filling the concave gaps
of the obstacles.
click to view
plan in a dense tunnel
with many sharp bends
click to view
Results on Collective
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.
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