# Balanced Parallel Exploration of Orthogonal Regions
## 4 Algorithms
### Room Exploration
The Leader must first make sure that the total work performed by agent \(i\) has not exceeded a ratio 3 between the Leader and agent \(i\), if agent \(i\) did exceed this ratio, then the Leader and agent swap roles and the Leader begins the Active part of RoomScan. If at least one other Inactive agent \(j\) is waiting with agent \(i\) then the Leader must check the ratio of work between agent \(i\) and all Inactive agents \(j\) to decide what to do with the stack. If agent \(i\)s work is within a ratio 4 of all other agents \(j\) then the Leader splits the stack in half, giving one part back to agent \(i\) and the other to the agent with lowest total work. After this, the Leader resets the threshold back to the minimum for agent \(i\) and signals agents \(i\) and \(j\) to become Active. Otherwise, if Inactive agent(s) \(j\) are waiting and \(i\) has exceeded the ratio, then the entire stack is given to the agent with lowest total work. Finally, if no other agent is Inactive and agent \(i\) is within a ratio of 4 between all the Active agents, then the stack is returned to agent \(i\) and agent \(i\) is signaled to remain Active. The Active subroutine (Algorithm 4) describes the Active agents' role as they are given a task by the Leader. The agent \(i\) tracks their current work, and their current threshold of work to determine when to return to the Leader. While the agent has task(s) to accomplish and the new work they have completed has not exceeded the current work threshold, the agent will take a task to accomplish. Agent \(i\) then takes the current task area and determines what are the smaller and larger dimensions of this task area. Then, agent \(i\) moves to the middle of the larger dimension and determines how many sub areas will be generated by traversing across the line that splits the task area. The sub areas are determined by the holes encountered through this line, such that holes touching the line and the boundaries of the original area determine new sub areas. We give an example of this step in Figure 3, as explained below. Figure 3: Splitting a Room with Holes. The reason for the room split is to parallelize the exploration task of the room, as the different agents will move to the various identified sub areas and explore them in parallel. The created sub areas are pushed to the stack, and each of them has the potential to be subdivided further. ```
/* Algorithm performed by each Leader until room is entirely explored */  Upon (agent \(i\) returning to meeting point with Leader)  set agent \(i\) to Inactive; ifagent \(i\) has a stack or Leader has a stack then ifagent \(i\) has a stack then  Leader takes stack of newly discovered areas from agent \(i\) and merges with current stack;  end if ifagent \(i\) is work exceeds ratio \(3\) above Leader's work then  Leader and agent \(i\) role swapped;  end if else ifmore than one agent is waiting without a stack then ifagent is work is within ratio \(4\) of all other agents' work which is at least 1/4 the initial traversal of \(i\)then  Leader splits stack into two parts of equal size;  Leader gives one part back to agent \(i\);  Other part is given to an Inactive agent \(j\) with lowest work;  Reset agent \(i\) work threshold to minimum;  Signal agents \(i\) and \(j\) to get Active;  end if else  Give stack to Inactive agent with lowest work;  end if  end if else ifagent \(i\) within ratio \(4\) of all other Active agents then  Give stack to agent \(i\);  Signal agent \(i\) to get Active;  end if  end while
```  
**Algorithm 3**Leader part of RoomScan  
For example, Figure 3 shows the vertical traversal line that goes through the room and splits it across the hole boundaries (holes labeled 1, 2, 3) into three subareas \(A\), \(B\), and \(C\). As shown in Figure 3, agent \(i\) does not have to change its traversal due to hole 1 as this hole is at least one point away from the traversal line. Agent \(i\) will have to change its traversal, due to hole 2 as this is along the traversal path and unknown to agent \(i\).