A coordination procedure is proposed for a multi-robot rescue system that performs real-time exploration over disaster areas. Real-time exploration means that every robot exploring the area always has a communication path to human operators standing by a monitor station and that the communication path is configured by ad hoc wireless networking. The proposed system procedure consists of the autonomous classification of robots into search and relay types and behavior algorithms for each class of robot. Search robots explore the areas and relay robots act as relay terminals between search robots and monitor station. The rule of the classification and the behavior algorithm refer to the forwarding table of each robot constructed for ad hoc networking. Computer simulations are executed with the decision-theoretic approach as the exploration strategy of search robots.