# Balanced Parallel Exploration of Orthogonal Regions
## 1 Introduction
The difficulty with this is the introduction of holes in the area. If the holes were not there, we could simply traverse the entire perimeter, divide the area into \(k\) equal partitions, and send the agents to their respective area. This is not possible with holes, as one or more of these partitions could consist mainly of holes, so the agents associated with those partitions would not perform \(O(N/k)\) leading to an imbalance of work between all agents. Thus, we developed an algorithm that handles the unknown holes in the area to maintain balanced work. The difficulty with these holes is that they are arbitrarily placed in the area. As a sub area was closed, if we simply divided the area into \(k\) partitions, then we cannot guarantee that all the agents perform near equal work as they can only communicate within a single grid point. For example, let's assume that the hole in a room of \(n\) points takes up all space except a single path around the area, then if partitioned, each agent encounters the same hole resulting in repeated work, which involves traversing around the hole and performing \(nk\) total work in the area instead of \(n\) total work. Moreover, as another example one agent may have to explore smaller number of holes (or total points) than other agents again resulting in imbalanced work. Figure 1: Example of Area and Generation of Rooms. To get the near equal work for each agent, we have introduced the concept of Leader, Active, and Inactive agent roles when an area is being closed (room created) and explored. These roles are determined based on the amount of work that was previously performed in other closed areas, the most, Leader, the least, Active, and all the rest, Inactive. Leader organizes the other agents to maintain their overall work when Active return to the Leader. Active performs traversal and when enough work has been completed, Active returns to the Leader to maintain equal work. Inactive remain with the Leader until an Active returns sharing its work making them Active. When the closed area is completed the agents return to being against the perimeter to traverse to the next closed area. When a room is discovered then all the agents move to explore the room. Inside the room, the exploration is performed in parallel by the agents while balancing their work. The reason of this approach, of exploring the rooms one after the other in sequence, is to have an online exploration of the whole area in one pass of the perimeter. Otherwise, we would first explore the whole perimeter, and then split the area into rooms, but this would have required to revisit the perimeter. Such a process would also not give us balanced work as large chunks of the area that most of the agents are sent might be made up of holes, unbalancing the agents' work. In our algorithm, the agents start along all adjacent to each other next to the perimeter. Then they traverse the perimeter maintaining a convoy. During the traversal, the agents create rooms to explore and map. The whole area is divided on the fly into a sequence of rooms, which are explored one after the other. In our approach, each room is a rectangular closed area which is identified on the fly at corners of the perimeter. When a room is identified the agents move immediately into the room together and explore all the points of the room by dividing the work among each other. A room may contain obstacles which are not immediately detected, and hence, the area of the room may not be able to be divided equally among the robots, which may cause imbalance of the work. To alleviate this problem, the agents start the room exploration slowly, and use exponential delay and meeting times when exploring the room to handle the unknown holes in the room. Agents that exceed their allocated work quota give future work to other agents to maintain parallelism and load balancing.