Home News About Us Contact Contributors Disclaimer Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Display Documents



ID: 202056.0, MPI für Informatik / Algorithms and Complexity Group
Multiple Robot Motion Planning = Parallel Processing + Geometry
Authors:Hert, Susan; Richards, Brad
Editors:Christensen, Henrik; Hager, Greg
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2002
Title of Proceedings:Sensor Based Intelligent Robots
Start Page:183
End Page:205
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Schloss Dagstuhl, Wadern, Germany
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2000-10-15
Review Status:not specified
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:We present two problems in multiple-robot motion planning that can be quite
naturally solved using techniques from the parallel processing community to
dictate how the robots interact with each other and techniques from
computational geometry to apply these techniques in the geometric environment
in which the robots operate. The first problem we consider is a load-balancing
problem in which a pool of work must be divided among a set of
processors in order to minimize the amount of time required to complete all
the work. We describe a simple polygon partitioning algorithm that allows
techniques from parallel processor scheduling to be applied in the
multiple-robot setting in order to achieve a good balance of the work.
The second problem is that of collision avoidance, where one must avoid that
two (or more) processors occupy the same resource at the same time.
For this problem, we describe a procedure for robot interaction that is
derived from procedures used to shared-memory computers along with a geometric
data structure that can efficiently determine when there are potential
robot collisions.
Last Change of the Resource (YYYY-MM-DD):2003-08-27
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-093AEDC50CC59658C1256A9C002B0A47-...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.