Research Abstracts - 2006

Distributed Area Search with a Team of Robots

Velin Tzanov, Jonathan Bachrach & Rangel Dokov

Introduction

Distributed Systems are a very large area of Computer Science. This is mostly due to two desirable properties of Distributed Systems: 1) they are more efficient and fault-tolerant than their non-distributed counterparts and 2) they are able to solve many problems that are otherwise unsolvable (such as providing infrastructure for scalable, high-traffic web sites). The main objective of this project is to apply the Distributed Systems paradigm to the world of Robotics, demonstrating how the two desirable properties can be applied to this area.

The particular problem we are tackling in this project is called Distributed Area Search: getting a team of robots to collaborate on the task of searching an area. Searching in this case is defined as looking for something specific throughout the whole area: it might be an object, a chemical agent, a given type of terrain, etc. This searching is accomplished through a specific scanning primitive, which checks whether the object is within some distance of the present position of the robot. In order to be as general as possible, we abstract away this primitive and focus on the rest of the operation, which is making sure that the robots have physically traveled within some distance of every possible location on the area.

Hardware and Infrastructure

Since Distributed Systems require a lot of hardware, each unit of hardware must be as cheap as possible in order to make the system cost-effective. That is why we have selected the Mark III robots [4], each of which costs less than $100. In addition to that, every robot is paired with an MIT Cricket [2], which provides a communication layer and the ability to measure the distance between every pair of robots.

Mark III Robot	MIT Mote Cricket

An extremely important parameter of the system is the presence (or lack) of localization infrastructure. Whether or not the robots have access to a GPS-like system is where this project splits into two completely different systems, each one of which emphasizes one of the two desirable properties of Distributed Systems.

Part I: Using a Global Positioning System

Since our robots are already equipped with Crickets, setting up a GPS-like system is relatively easy [2]. All we need is some (at least three) stationary Crickets, mounted on various locations around the area to be covered. Using the Crickets' ability to measure distances between one another and solving a simple system of equations involving the distances from a robot to three or more stationary Crickets, we are able to infer the coordinates of any robot on a coordinate system constructed by the stationary Cricket nodes. This gives universal (i.e., common for everyone) coordinates to every robot and thus enables us to abstract away the localization system as a black box.

Given the black-box localization system and our ability to discretize the world into a grid (since the search primitive covers a circle of a given area), we can reduce the problem to coordinating the movements of a number of agents on this grid map, so that they visit every reachable grid point in as little time as possible. The aim of our work in this part of the project is to increase the efficiency and fault-tolerance of the system by making it distributed. Our metric of success is the time that an algorithm takes and the parameters we use are the following:

• S - total size of the area (number of reachable grid points that are not obstacles)
• R - number of (surviving) robots
• V - number of rooms (defined as continuous convex areas, without any obstacles inside)
• D - diameter (largest distance between two points) of the whole area
• W - sum of the diameters of all rooms

Most trivial algorithms for organizing the robots either fail the fault-tolerance test (i.e., the whole system fails if one or more of the robots fail), or they are inefficient (i.e., they result in unacceptably high times). The best trivial algorithm we have found so far is the following greedy algorithm: Always go to the closest uncovered grid point, which is not anyone else's destination. This algorithm has a lower bound of Ω(S/R + W)

Our best algorithm so far builds on two fundamental ideas. First, having the robots understand the notion of a room (convex, uninterrupted free space), so that they can do things like claiming "ownership" of a room. Second, the idea presented by Burgard et al. [1] of splitting the remaining labor in a way that makes the robots diverge whenever possible. This approach effectively reduces the problem to a higher-level problem of having the robots cover (i.e., walk on every node of) a graph, where a node is defined as a room and two nodes are connected with an edge, whenever the two underlying rooms are connected. The cost of a node in this reduced problem is the diameter of the underlying room and the loss function by which we evaluate the algorithm is the sum of costs incurred by the different robots until the end of the algorithm. We are presently analyzing the worst-case scenarios on this reduced problem, as well as reasonable definitions of average-case scenarios. Our goal is to prove a theoretical bound on our algorithm on the original problem (at least in the average case, but hopefully in the worst case too) that would make it more scalable than the greedy algorithm. The intuitive test we use is scaling S, V and W quadratically and scaling D and R linearly and then making sure that the time complexity grows less than quadratically (as the greedy algorithm has a complexity growing quadratically in this scenario). For example, acceptable bounds would be O( (S + W*log(R)) / R), O( (S + min(W*R, D*R)) / R) or even O( (S + min(W*R^0.5, D*V, D*R^1.5)) / R).

Simulated GPS based Distributed Area Search with Six Robots

Part II: An Autonomous System

In this part of the project, we are building a system that is completely autonomous (i.e., no localization or other infrastructure at all). The goals in this part are completely different from the goals in the first part. Instead of efficiency and fault-tolerance this time we are limiting ourselves only to making the Area Search system possible at all.

The grand problem in such autonomous systems is that robots' coordinates inevitably drift away with time and eventually the robots lose track of where they are relative to their previous positions. This makes the Area Search problem practically unsolvable with a limited number of robots, as then the robots may have to disconnect themselves with the origin and then return back to it (say, to take another branch of the maze). With such a task they can never guarantee that they will find the way back at all (as they will effectively lose their absolute coordinates), and thus, they will fail at covering the area completely.

We remedy this problem by introducing a distributed system, which requests additional robots whenever the present number is not enough for covering the area reliably. The main ideas in the part of the project are taken from the works of Rekleitis et al. [5] and Kurazume et al. [3]. The first paper introduces the idea of having mobile robots serve as temporary stationary landmarks. The second paper describes a strategy for searching an area of arbitrary shape by dividing the area into triangles (i.e., triangulation), representing these triangles as a connected topological graph and then searching this graph in a DFS fashion.

Our system uses the robots to build a triangulation of the area and then searches every triangle in a fashion very similar to the first system described above (with the three corners of the triangle serving as the GPS system). In addition to that (unlike the case in the original paper by Kurazume et al.), every time there is a branching of the topological graph, we leave two of the robots as stationary landmarks, marking the location of the branch. This enables the robots that continue on one of the branches to first recognize the branching point on their way back, and second, to realize that they have closed a loop in the event that they return to the branching point through a different branch. This allows the robots to always keep track of where they are on the topological graph, and thus, it enables them to make sure every bit of the area is covered.

It is notable that the robots still lose track of their global coordinates, but this is not a problem in our case. Because of the fact that robots in adjacent triangles effectively "hold hands", the local coordinates of the mobile robots (coordinates relative to the positions of their stationary neighbors) remain robust: they are computed by the same simple and reliable system of equations used for the GPS-style localization in Part I. Having robust local (relative) coordinates ensures that there will be no holes or cracks in the coverage of the area of or in between triangles, which insures that the whole area will be covered completely.

Since robots are required to remain behind only in the event that there is a branching in the topological graph of triangles, the number of robots required to complete the task is O(D), where D is the largest number of branching points on any simple path on the topological graph.

References:

[1] W. Burgard, M. Moors, D. Fox, R. Simmons, S. Thrun. Collaborative Multi-Robot Exploration. IEEE ICRA 2000

[2] N. Priyantha, A. Chakraborty, H. Balakrishnan. The Cricket Location-Support system, Proc. 6th ACM MOBICOM, Boston, MA, August 2000.

[3] R. Kurazume, S. Nagata, S. Hirose. Cooperative Positioning with Multiple Robots. ICRA, 1994

[4] Mark III OOPic Version. http://www.junun.org/MarkIII/Info.jsp?item=27

[5] I. Rekleitis, G. Dudek, E. Milios. On Multiagent Exploration. Vision Interface 1998, pages 455-461, Vancouver, Canada, June 1998.