# Balanced Parallel Exploration of Orthogonal Regions
## 4 Algorithms
### Room Exploration  
After front agent in perimeter scan successfully reaches \(\delta^{\prime}\) and returning to the other agents, a room is found, the room scan is invoked. Now that the dimension of the room is known, the agents could have divided the room into \(k\) equal areas and begin to search. However, given that the holes are arbitrarily placed, it can be such that the assignments of some agents may contain no work. The other agents cannot detect this until being within communication range. With this, it can also be such that the agents repeat the same work when traversing around a hole in the area. Therefore, to maintain balanced work, we introduce agent roles and a slow start to increase parallelism. The agents are set to the roles of Leader, Active, or Inactive. All agents are within communication range at this point and communicate their work with the other agents to determine who has the most work, Leader, and the one with least work, Active, and the remaining, Inactive. If two share work then that agent with the lower ID will be Leader. The purpose of the Leader is to maintain a ratio of work between all agents to balance the work performed by each agent. The Active agent is given a task in the form of a stack of areas to explore, and performs the exploration until a work threshold is reached. This stack is initially a single task consisting of the entire room. As the Active agent performs the traversal it will split the current task and push it back on the stack. A task is two corner points of the perimeter of the area they are required to explore. In giving the Active agent these two points, the agent can discern the rectangle of exploration. The Inactive agents are in a convoy by the Leader waiting for the Leader to give them a task and become Active. The allocation of the work to the agents is performed in a balanced way, such that those agents with lower work are given work and those that exceed the work of lower working agents are made Inactive. If this is the first room attempted to close then no agent has any room work so it is arbitrary which agent is set to Leader, Active, or Inactive. Otherwise, the agent with the most room work is set to the Leader, yellow 'x' in Figure 3, the one with the least room work is set to Active, black 'x' in Figure 3, and the rest begin as Inactive, white 'x' in Figure 3.  
The work threshold of an Active agent is initially set to a value \(d_{max}\) that is determined by the longest length of the room and the cost of traversing around holes on a straight path, discussed in more detail in Section 5 where we analyze the algorithm. As the room exploration progresses, the work threshold exponentially increases to accommodate the expected work in the newly discovered areas. The amount of work threshold only increases when work is not shared or given to another agent. This is due to the fact that if no other agent was there, then doubling the amount of work to return will maintain equal work among the agents. Gradually, Inactive agents are becoming Active as more area is discovered in the room. The Leader subroutine (Algorithm 3) describes the Leader's role as Active agents return to the Leader. The Leader's job is to maintain the remaining work between itself and the Active and Inactive agents. When an agent \(i\) has performed work that exceeds its threshold or it ran out of tasks to perform, it returns to communication range of the Leader. In performing this the agents repeats the same amount of work as the threshold to return, but with exponentially increasing work threshold the agent will perform more new work than the cost to return to the Leader. This way, load balancing can be achieved at a faster pace. It is necessary to return to communication with the Leader to enable the Leader to balance the work between the Inactive agents. If the agent \(i\) has a stack remaining, or the Leader has a stack, then the Leader takes agent \(i\)s stack and merges it with its own.