22-09-2012, 12:38 PM
Smooth and Efficient Obstacle Avoidance for a Tour Guide Robot
[attachment=34346]
Abstract
We present the local path planning and obstacle
avoidance method used on the autonomous tour-guide robot
RoboX. It has proven its value during a 5 month operation of
ten such robots in a real-world application, a very crowded
exhibition. Three known approaches (DWA, elastic band,
NF1) have been integrated into a system that performs
smooth motion efficiently, in the sense of computational effort
as well as goal-directedness. Apart from modifications to the
DWA and the elastic band, we present the formulations that
allow this fusion.
INTRODUCTION
A tour-guide robot has to be able to move autonomously,
acquire the attention of the visitors and
interact with them efficiently. Usually, the environment
is known and accessible, but the visitors make it highly
cluttered and dynamic.
This paper presents an implementation of path planning
and obstacle avoidance for RoboX (fig. 1), an autonomous
tour-guide robot developed at the Autonomous Systems
Lab for Expo.02 (the Swiss national exhibition that took
place from May 15th to October 20th 2002). RoboX’s
navigation subsystem comprises an embedded Power PC
G3 at 380 MHz running the XO/2 real-time operating
system, two SICK laser scanners, 8 contact sensors with
soft bumpers and a differential drive architecture.
The Robotics pavilion where RoboX operated was
visited by 400 persons per hour, at a density of 100 visitors
on 300m2. This can be likened to a railway station at rushhour
(fig. 2). RoboX had to move with, against and across
the flow of people to accomplish its tour-guiding task. And
it should never stop moving, lest the visitor lose interest.
AIM AND APPROACH
A tour-guide robot faces certain requirements. The
collision risk must be low and the eventual effects of
a collision be harmless. Smooth motion is important, as
visitors anticipate movement when they follow the guide.
The obstacle avoidance control loop should be fast in
order to not only run in real-time, but also leave enough
processing resources to other modules such as localization,
sensor acquisition, web server and motor control.
Collision Prediction
The collision prediction in [5] calculates the distance
to travel before hitting an obstacle. This is not applicable
to pure rotations because any collision would seem
instantaneous. We solved this problem by using the time
until collision, which does not present such a singularity.
As a side effect, the same geometric distance appears
closer at high speeds, effectively adding a buffer distance
proportional to speed.
DYNAMIC WINDOW
The DWA generates actuator commands such that the
robot does not collide with obstacles, the commands do
not violate the dynamic capabilities of the actuators and
the robot follows the elastic band.
In our implementation, the robot shape’s (polygon) is
defined at startup (instead of being hard-coded). Additionally,
a significant speed-up and a predictable maximum
cycle time have been achieved by calculating a lookup
table for the collision prediction, also during startup.
This vital part of the DWA would otherwise constantly
require expensive computations of varying numbers of
intersections between circles and lines, up to 90000 on
RoboX. A similar idea can be found in [11].
Objective Functions
The DWA chooses among admissible commands by
maximizing an objective function on the sampled q˙ l q˙r
space. The usual sub-objectives are used: Heading, speed
and clearance.
The heading objective whead makes the robot follow the
elastic band or, once the goal radius has been reached,
orient itself along a specified direction.
The speed objective wspeed can be switched at run-time:
High objective values for high forward speeds to move
forward, preferring high backward speeds make the robot
reverse, and high objective values for low translational
speeds to turn on the spot. This is used to follow paths
based on holonomic assumptions while consistently using
the DWA to generate actuator commands.
The clearance objective wclear tends to maximize the
space between robot and obstacles. It measures by how
much the collision prediction exceeds the braking time
for q˙, see (3) and (4).
FUTURE WORK
The current implementation takes advantage of the specific
environment. Ongoing research at the Autonomous
Systems Lab aims at making the motion planner more
generally applicable.
From time to time, the lack of sensory memory causes
an oscillating replanning behavior. This was not a problem
at Expo.02, but future applications might be less forgiving
in this aspect. Integrating a memory along the lines of the
local perceptual space mentioned in [7] should alleviate
this problem.
Another issue concerns the simplifications used for the
elastic band and how the robot can get stuck when turning
into narrow corridors. Here, the non-holonomic nature of
the differential drive should be taken into account in the
plan representation. A solution which does so only at
critical points along the elastic band seems promising, as
we aim to preserve the computational efficiency of the
simplified elastic band.
CONCLUSION
We have presented a novel combination of known
algorithms for mobile robot path planning and control. It
was shown that our combination performs well enough
to be deployed in a challenging long-term real-world
application.
Using a time-based clearance measure solves a singularity
present in the original DWA. We base the dynamic
window in physically meaningful representations and use
the speed objective as a means to safely switch between
overall robot behaviors.
[attachment=34346]
Abstract
We present the local path planning and obstacle
avoidance method used on the autonomous tour-guide robot
RoboX. It has proven its value during a 5 month operation of
ten such robots in a real-world application, a very crowded
exhibition. Three known approaches (DWA, elastic band,
NF1) have been integrated into a system that performs
smooth motion efficiently, in the sense of computational effort
as well as goal-directedness. Apart from modifications to the
DWA and the elastic band, we present the formulations that
allow this fusion.
INTRODUCTION
A tour-guide robot has to be able to move autonomously,
acquire the attention of the visitors and
interact with them efficiently. Usually, the environment
is known and accessible, but the visitors make it highly
cluttered and dynamic.
This paper presents an implementation of path planning
and obstacle avoidance for RoboX (fig. 1), an autonomous
tour-guide robot developed at the Autonomous Systems
Lab for Expo.02 (the Swiss national exhibition that took
place from May 15th to October 20th 2002). RoboX’s
navigation subsystem comprises an embedded Power PC
G3 at 380 MHz running the XO/2 real-time operating
system, two SICK laser scanners, 8 contact sensors with
soft bumpers and a differential drive architecture.
The Robotics pavilion where RoboX operated was
visited by 400 persons per hour, at a density of 100 visitors
on 300m2. This can be likened to a railway station at rushhour
(fig. 2). RoboX had to move with, against and across
the flow of people to accomplish its tour-guiding task. And
it should never stop moving, lest the visitor lose interest.
AIM AND APPROACH
A tour-guide robot faces certain requirements. The
collision risk must be low and the eventual effects of
a collision be harmless. Smooth motion is important, as
visitors anticipate movement when they follow the guide.
The obstacle avoidance control loop should be fast in
order to not only run in real-time, but also leave enough
processing resources to other modules such as localization,
sensor acquisition, web server and motor control.
Collision Prediction
The collision prediction in [5] calculates the distance
to travel before hitting an obstacle. This is not applicable
to pure rotations because any collision would seem
instantaneous. We solved this problem by using the time
until collision, which does not present such a singularity.
As a side effect, the same geometric distance appears
closer at high speeds, effectively adding a buffer distance
proportional to speed.
DYNAMIC WINDOW
The DWA generates actuator commands such that the
robot does not collide with obstacles, the commands do
not violate the dynamic capabilities of the actuators and
the robot follows the elastic band.
In our implementation, the robot shape’s (polygon) is
defined at startup (instead of being hard-coded). Additionally,
a significant speed-up and a predictable maximum
cycle time have been achieved by calculating a lookup
table for the collision prediction, also during startup.
This vital part of the DWA would otherwise constantly
require expensive computations of varying numbers of
intersections between circles and lines, up to 90000 on
RoboX. A similar idea can be found in [11].
Objective Functions
The DWA chooses among admissible commands by
maximizing an objective function on the sampled q˙ l q˙r
space. The usual sub-objectives are used: Heading, speed
and clearance.
The heading objective whead makes the robot follow the
elastic band or, once the goal radius has been reached,
orient itself along a specified direction.
The speed objective wspeed can be switched at run-time:
High objective values for high forward speeds to move
forward, preferring high backward speeds make the robot
reverse, and high objective values for low translational
speeds to turn on the spot. This is used to follow paths
based on holonomic assumptions while consistently using
the DWA to generate actuator commands.
The clearance objective wclear tends to maximize the
space between robot and obstacles. It measures by how
much the collision prediction exceeds the braking time
for q˙, see (3) and (4).
FUTURE WORK
The current implementation takes advantage of the specific
environment. Ongoing research at the Autonomous
Systems Lab aims at making the motion planner more
generally applicable.
From time to time, the lack of sensory memory causes
an oscillating replanning behavior. This was not a problem
at Expo.02, but future applications might be less forgiving
in this aspect. Integrating a memory along the lines of the
local perceptual space mentioned in [7] should alleviate
this problem.
Another issue concerns the simplifications used for the
elastic band and how the robot can get stuck when turning
into narrow corridors. Here, the non-holonomic nature of
the differential drive should be taken into account in the
plan representation. A solution which does so only at
critical points along the elastic band seems promising, as
we aim to preserve the computational efficiency of the
simplified elastic band.
CONCLUSION
We have presented a novel combination of known
algorithms for mobile robot path planning and control. It
was shown that our combination performs well enough
to be deployed in a challenging long-term real-world
application.
Using a time-based clearance measure solves a singularity
present in the original DWA. We base the dynamic
window in physically meaningful representations and use
the speed objective as a means to safely switch between
overall robot behaviors.