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.
Robot Software
Robot Software is used for programming robots to insturt the device to perform certain autonomous tasks.
Pendant Stations
Pendant stations are sophisticated, handheld terminals that are used to control robot or machine movements from point to point, within a determined space. They consist of a hanging control console furnished with joysticks, push-buttons or rotary cam switches.  
Drilling and Tapping End Effectors
Drilling and tapping end effectors attach to the end of a robotic arm, and perform machining of holes and threads in a target material. The effectors are adapted to the end of an articulating robotic arm, often via an interfacing device called an automated tool changer (ATC). A common application for drilling and tapping end effectors is on automobile manufacturing assembly lines.

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...

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...

Michael Erdmann, Carnegie Mellon University, Pittsburgh, PA, USA 1 Introduction As a robotic hand grasps an object of unknown shape, the object may slip in the robot's fingers. If the robot can infer...

Product Announcements