I. Rekleitis, G. Dudek The problem of exploring an unknown environment and constructing a map is central to mobile robotics. Existing approaches that have been proposed for this problem range from idealized solutions involving perfect virtual robots to practical solutions with real robots. The range of environment and terrain types that have been considered has been similarly varied. These range from sets of polygons on the plane and abstract 3D shapes used in geometric explorations up to real world environments such as office buildings, lunar surfaces, underground mines, and underwater terrains. This work deals with questions of efficiency and feasibility of environment exploration by a group of 2 or more robots. In preliminary studies, we model the world as a collection of closed 2-dimensional curves and have developed new algorithms for exploring an unknown environment using cooperating mobile agents. Two autonomous robots with limited sensing abilities are used, and we present some theoretical results with a configuration that closely models the uncertainty of the real world. By using a team of robots, problems that would be encountered by a single robot can be avoided.