Transcript Blue Lines and Gradients - University of Nebraska Omaha

MULTI-ROBOT COVERAGE WITH DYNAMIC
COVERAGE INFORMATION COMPRESSION
Zachary Wilson
Computer Science Department
University of Nebraska, Omaha
Advisor: Dr. Raj Dasgupta
MULTI-ROBOT TERRAIN COVERAGE PROBLEM
•
•
Problem statement: How to coordinate a set of
robots so that they can completely cover an initially
unknown region within which they are deployed
Encountered in many applications of robotic
systems
–
–
–
–
Detecting landmines for humanitarian demining
Unmanned search and rescue following disasters
Extra-terrestrial exploration
Domestic applications: automated lawn mowing,
vacuum cleaning, etc
COMMUNICATION OVERHEAD IN
MULTI-ROBOT TERRAIN COVERAGE

Coverage has to be done efficiently
•
•
Reducing time, energy (battery) consumed
Reducing the amount of repeated coverage of the same region by multiple robots
COMMUNICATION OVERHEAD IN
MULTI-ROBOT TERRAIN COVERAGE

Coverage has to be done efficiently
•
•
Reducing time, energy (battery) consumed
Reducing the amount of repeated coverage of the same region by multiple robots
I have to tell other
robots what regions I
have covered till now
so that they don’t recover those
COMMUNICATION OVERHEAD IN
MULTI-ROBOT TERRAIN COVERAGE

Coverage has to be done efficiently
•
•
Reducing time, energy (battery) consumed
Reducing the amount of repeated coverage of the same region by multiple robots
I have to tell other
robots what regions I
have covered till now
so that they don’t recover those
I should also know
what regions other
robots have covered
till now, so that I can
avoid and not recover those regions
COMMUNICATION OVERHEAD IN
MULTI-ROBOT TERRAIN COVERAGE

Coverage has to be done efficiently
•
•
Reducing time, energy (battery) consumed
Reducing the amount of repeated coverage of the same region by multiple robots
•
I have to tell other
robots what regions I
have covered till now
so that they don’t recover those
I should also know
what regions other
robots have covered
till now, so that I can
avoid and not recover those
How much info
do robots
communicate?
–
–
–
Maps exchanged
between every
pair of robots
Repeated at
certain intervals
Map of covered
region for each
robot keeps
growing with time
COMMUNICATION OVERHEAD IN
MULTI-ROBOT TERRAIN COVERAGE

Coverage has to be done efficiently
•
•
Reducing time, energy (battery) consumed
Reducing the amount of repeated coverage of the same region by multiple robots
•
I have to tell other
robots what regions I
have covered till now
so that they don’t recover those
I should also know
what regions other
robots have covered
till now, so that I can
avoid and not recover those
How much info
do robots
communicate?
Maps exchanged
between every
pair of robots
– Repeated at
certain intervals
– Map of covered
region for each
robot keeps
growing with time
Very high
communication
overhead
–
COMMUNICATION OVERHEAD IN
MULTI-ROBOT TERRAIN COVERAGE

Coverage has to be done efficiently
•
•
Reducing time, energy (battery) consumed
Reducing the amount of repeated coverage of the same region by multiple robots
•
I have to tell other
robots what regions I
have covered till now
so that they don’t recover those
I should also know
what regions other
robots have covered
till now, so that I can
avoid and not recover those
How much info
do robots
communicate?
–
–
–
Maps exchanged
between every
pair of robots
Repeated at
certain intervals
Map of covered
region for each
robot keeps
growing with time
More energy (battery),
more calculations,
more time
MULTI-ROBOT COVERAGE INFORMATION
SHARING

Every robot covers a certain region on its own (autonomously)
MULTI-ROBOT COVERAGE INFORMATION
SHARING



Every robot covers a certain region on its own (autonomously)
Communicates this coverage map to other robots within
communication range
Receives other robots’ coverage maps
This is the region I
have just covered
This is the region I
have just covered
MULTI-ROBOT COVERAGE INFORMATION
SHARING



Every robot covers a certain region on its own (autonomously)
Communicates this coverage map to other robots in
communication range
Receives other robots’ coverage maps
We need to
combine these
maps
This is the region I
have just covered
This is the region I
have just covered
...without
increasing the
number of data
points (vertices)
used to store the
combined map
MULTI-ROBOT COVERAGE INFORMATION
SHARING



Every robot covers a certain region on its own (autonomously)
Communicates this coverage map to other robots in
communication range
Receives other robots’ coverage maps
We need to
combine these
maps
This is the region I
have just covered
This is the region I
have just covered
...without
increasing the
number of data
points (vertices)
used to store the
combined map
Otherwise,the maps would keep becoming larger and larger as we cover more
regions needing more comms...more battery power and time
COVERAGE INFORMATION COMPRESSION



Take two or more
polygons
Calculate their
bounding convex
polygon – called
convex hull
Make an
approximation of the
convex hull that has a
fixed (constant)
number of points –
using min-e algorithm
COVERAGE COMPRESSION: OVERLAPPING
REGIONS

Fitness function used to
accept or discard fitted
polygon
 Adjusting weights gives
different amount of
repeated coverage based
on application domain

Landmine detection:
Repeated coverage is not
fatal, could improve
detection accuracy
Pesticide application:
Repeated coverage can
kill crops
SIMULATION ENVIRONMENT


The Corobot platform:
 Stargazer localization
module (gives 2-d
coordinates)
 5 IR sensors (for avoiding
fixed obstacles – walls)
 640x480 camera (used for
avoiding moving objects –
other robots)
 Wi-Fi wireless comms.
 10 AH battery (about 2030 min. life)
We used 4 simulated test
environments:
 No obstacles
 10% obstacles
 25% obstacles
 Corridor with rooms.
SIMULATION RESULTS: HOW WELL DOES THE
COVERAGE PERFORM
• Snapshots of coverage achieved with 2, 3 or 4
robots
• 20 X 20 meter2 arena
• 2 hours of real time
Amount of (instances
of) communication
between robots in
different scenarios
SIMULATION RESULTS: HOW WELL DOES THE
COVERAGE PERFORM

Coverage Efficiency:




The first graph shows the
useful distance traveled while
doing coverage.
The second graph shows the
overhead distance, e.g.,
moving between regions while
not doing coverage.
We see that as the number of
obstacles increases, the
amount of overhead increases
while the amount of coverage
decreases.
Peak efficiency is about 2.67
meters of coverage for every
meter of overhead (72%).
SIMULATION RESULTS: HOW WELL DOES THE
INFORMATION COMPRESSION WORK

Compression Efficiency:



The first graph shows the
compression offered by standard
error-free ZIP compression from 4
to 200 data points.
The second graph shows the
integrity of data compressed with
the min-ε algorithm for different
statically-sized approximations.
With a 200 point data-set:


ZIP algorithm: 2% decrease in size,
0% loss
Min-ε algorithm: 98% decrease in
size, 10% loss (with a 4 point
approximation)
CONCLUSIONS AND FUTURE WORK

Conclusions:
Efficient coverage through communication
 Efficient communication through compression
 Efficient compression through approximation
 Hardware implementation also done on Corobot robots


Future work:
More efficient region selection
 Neural-network based fitness determination
 Comparison with other techniques


Acknowledgements: We are grateful to the U.S. Office of Naval Research for sponsoring this
research through the COMRADES project