# Balanced Parallel Exploration of Orthogonal Regions
## 1 Introduction  
In mobile agent research, there are two types of problems: coverage and exploration. Coverage is concerned with patrolling an area, i.e., how to organize the agents so they can maximize the area they can view while still being able to be in contact range of the other agents in a chain [1; 2; 3; 4]. This assumes that the agents already have full understanding of the area to be able to determine the best course of action to achieve these goals. On the other hand, exploration works with a previously unknown area, and attempts to map all the area. Applications of area exploration include to find survivors quickly, setup a network, or to rendezvous distributed agents. Hence, exploration is a more fundamental problem which may also be used to solve coverage problems. To explore an unknown area, previous papers have used sensor networks [5; 6; 7; 8; 9]. This style of exploration has the agents placing static sensors at intervals of the area to create a network and cover the explored area. The sensors then can be used by the agent to find the area boundaries and store information from previous scans of the robots that can help to explore new parts of the area. The agent itself has little memory and relies heavily on the sensors. The sensors must be carried by the agents adding weight that inhibits the mobility. In this paper, we present a set of algorithms to solve area exploration without using auxiliary static sensor nodes, but rather, with just self-reliant mobile agents. The area is an orthogonal closed region that is made up of horizontal and vertical walls. This area is then discretized into \(N\) traversable points that are connected to their neighboring points in the cardinal directions. An agent moves north, east,south, or west, on the neighbor points from its current position, whenever these points are available. The number \(N\) is not known to the agents. The agents discover the area and the number of points during exploration. The area contains holes, non-traversable locations, which are randomly distributed in the area; for example, Figure 1 depicts black holes in the area. These holes are rectangular and have a length and width within an aspect ratio \(a\). The agents begin in a chain along the perimeter of the area, Figure 1 black \(xs\). To close area 1, Figure 1, at the time of reaching the first and second corner a room cannot be closed, it is only after reaching the third corner in this scenario to close a room. This is due to the agents not knowing the composition of the room causing them to have a previously visited \(x\) coordinate with the third corner. All agents are assumed to be the same with equal traversal ability, communication range, and total memory. An agent occupies a single point at a time and can move one point in the cardinal directions in which the point has connection. We assume that it takes one time step to move point to point. The agents have enough memory to map the entire area (i.e., find coordinates of explored points) which can be shared between agents. To share area information, the agents must be within adjacent points, or in a connected chain in which there is a sequence of adjacent pairs of agents. Agents share information on their total area traversed as well as the orientation of the area. Through this process, agents can make decisions, such as room scan roles, and which one will be the front agent for perimeter scan. These constraints on the agents enables them to not rely on sensors to have knowledge of the unexplored area. The work of an agent is the total number of points it traverses. Each agent keeps track of the work it has performed, and the goal is to maintain balanced work among the agents. The main goal is to explore an unknown orthogonal region of \(N\) points with \(k\) mobile agents in parallel in order to reduce the work, which is the total number of points visited, of each agent to explore the area to \(O(N/k)\), namely balancing the work and total exploration time \(O(N/k)\).