When a disaster like an earthquake occurs, human attendance may become dangerous and it is better to use robots for rescue mission. A time limitation exists in time of rescuing victims and robots batteries lives. Rescue robots should explore environment as fast as possible to maximize the chance of finding victims in the limited time. Rescue robots share a map to achieve this goal and to cooperate their exploration. The gathered data and its representation can be an occupancy grid map that shows occupied, free or unexplored areas. In addition victims locations and the path to reach them can be shown on the map. Using multiple robots instead of one robot may lead to some difficulties that should be considered, like incompatibility in robots information, collision of robots to each other and merging robots maps. In this thesis, a new map named “Scan History Network” is introduced to improve coordination of a team of exploring robots. This method uses a more suitable criterion in selecting exploration targets. The benefit of using scan history network for coordinating multiple robots over using nearest frontiers as robots’ goals in occupancy grid map in usual approaches is that robots try to detect “less scanned” points in the environment by keeping a history of robots sca then every robot selects one of these points as its target and tries to plan a suitable path to reach it. The target of each robot is selected, separated from others with an acceptable distance to have better coverage and exploration of environment. Common approaches set more priority for nearer frontiers when selecting them. Although this criterion has been mentioned in the new approach, it’s not given high priority. The main goal of the new approach is to optimize robots’ exploration and overcoming time limitation and at the same time keeping efficiency. Also, during map building, a Graph-Oriented Map in the environment is created in which nodes are junctions in the environment that are the main structural parts in the area. This map can be used in future navigations of robots, so repetitive processes are not needed. Therefore exploration and path-planning is performed faster. An improved approach is introduced to detect junctions. In this method, unlike usual approaches that obtain graph-oriented map from processing occupancy grid map, nodes information that are junction locations are gathered directly from the environment by “detecting Gaps” in laser range scanners data. Keywords: Coordinated Exploration, Multi-Robots, Scan History Network, Graph-Oriented Map, Path-Planning, Mapping, Localization, SLAM