From Algorithmic and Computational Robotics: New Directions: The Fourth Workshop on the Algorithmic Foundations of Robotics

Zack J. Butler, Carnegie Mellon University, Pittsburgh, PA

Alfred A. Rizzi, Carnegie Mellon University, Pittsburgh, PA

Ralph L. Hollis, Carnegie Mellon University, Pittsburgh, PA

Complete coverage of an unknown environment is a valuable skill for a variety of robot tasks such as floor cleaning and mine detection. Additionally, for a team of robots, the ability to cooperatively perform such a task can significantly improve their efficiency. This paper presents a complete algorithm DC R (distributed coverage of rectilinear environments) which gives robots this ability. DC R is applicable to teams of square robots operating in finite rectilinear environments and executes independently on each robot in the team, directing the individual robots so as to cooperatively cover their shared environment relying only on intrinsic contact sensing to detect boundaries. DC R exploits the structure of this environment along with reliable position sensing to become the first algorithm capable of generating cooperative coverage without the use of either a central controller or knowledge of the robots' initial positions. We present a completeness proof of DC R, which shows that the team of robots will always completely cover their environment. DC R has also been implemented successfully in simulation, and future extensions are presented which will enable instantiation on a real-world system.

1 Introduction

The coverage problem, that of planning a path for a sensor, effector, or robot to reach every point in an environment, is one that appears in a...

Products & Services
Robots (Industrial)
Industrial robots are programmable manipulators that contain rotary and/or prismatic joints in order to perform precise, repetitive movements. They are designed to move parts, tools, materials, and devices through variable, programmed motions. Types of products include articulated, Cartesian, cylindrical, gantry, parallel (hexapods), SCARA, and spherical robots.
Robot Repair Services
Robot repair services provide maintenance and repair for robots and robotic components.
Arc and Resistance Welding Equipment
Welding machines and joining machines include all manner of devices used for welding, brazing and soldering.
Collision Sensors
Collision sensors are used to protect robots from colliding with other objects. Noncontact sensors are used to help robots avoid these collisions.
Teach Pendants
Teach pendants are a specific type of industrial pendant. They are devices equipped with switches and dials used to control a robot's movements to and from desired points within a determined space.

Topics of Interest

Jonathan E. Luntz, University of Michigan, Ann Arbor, MI William Messner, Carnegie Mellon University, Pittsburgh, PA Howie Choset, Carnegie Mellon University, Pittsburgh, PA Distributed manipulation...

Devin J. Balkcom, Carnegie Mellon University, Pittsburgh, PA Matthew T. Mason, Carnegie Mellon University, Pittsburgh, PA We consider a differential drive mobile robot: Two unsteered coaxial wheels...

Chapter List Sensor Based Motion Planning: The Hierarchical Generalized Voronoi Graph Integrating Configuration Space and Sensor Space for Vision-Based Robot Motion Planning Howie Chos, Carnegie...

Pankaj Agarwal Duke University Srinivas Akella Rensselaer Polytechnic Institute Nancy Amato Texas A&M Boris Aronov Polytechnic University Devin Balkcom Carnegie Mellon University Matthew...

At first glance, they appeared to be adorable Sony Aibo robotic dogs. In reality, they were fiercely competitive soccer-playing bots vying to be top dog in the 2003 Robocup American Open held at...