# Balanced Parallel Exploration of Orthogonal Regions
## 2 Related Work  
The most related previous work is solving a similar problem, using \"oriented disjoint rectangular obstacles\" in an \(n\times n\) grid [10]. In this, the agents also use only local information, but with the oriented obstacles, all obstacles follow an oriented pattern that allow the area to be divided into similarly shaped partitions. Our problem has arbitrarily located rectangular obstacles of ratio \(a\). With this, our problem or theirs cannot be reduced to the same problem. For this reason, a new algorithm had to be developed not only to traverse the entire area, as it does not follow their \(n\times n\) grid rules with disjointed obstacles, and another algorithm for the room, as the obstacles do not follow the same constraints. Finally, our focus is on balanced work as well as parallel while theirs is only on parallel work. The most closely related topics in the literature are \"map merging\", concerned with multiple-robot simultaneous localization and mapping (SLAM) [11], and \"map synchronization\" [12], where the agents share the map information of the area explored. Agents are not assumed to be together and use probabilistic generalized Voronoi diagram to, \"achieve fast and accurate map fusion for large maps\"[11]. In map synchronization, agents can form into subgroups that are close enough to have the same map, while other agents that are not will synchronize maps when they approach [12]. This is also similar to Frontier based, which is concerned with exploring all points of a grid area in a minimum amount of time [13; 14]. However, these do not consider load balancing the work of the agents as we do here. One topic of focus on this area is agents that can fail. This can be through \"black hole\" or \"black link\" in an edge or link in a sensor network [15], or the agent itself can fail [16]. To be able to explore the entire area, the number of sensors must be more than the number of edges plus two times the number of links [15]. With using \"pheromones\", Levy Walk was determined to outperform random walk when exploring, especially when failure prone agents are introduced [16]. Exploration is also a topic of interest in communication networks. Ad-Hoc networks are constantly changing, mobile agent routing leaves information at nodes it visits and reads the information that is left at a node [17; 18]. In this way, the agents can cooperate much like ants leaving information to share with others when looking for food. When speed of network changes increases the delay decreases but roughly only 68% of packets are received and this amount drops greatly as speed increases [17]. MAR [18] can perform at greater speeds with the same percentage of packets received but less delay. Machine learning algorithms have also been used for mobile agent exploration. Q-Learning has been used as a \"Human-like\" learning algorithm to manage energy, avoid obstacles, working towards goals, and following a line [8]. Another implementation used online-learning Bayesian network to predict terrain range and magnetic field intensity [19]. A second online-learning method used Gaussian Processes [20]. In this learning, decentralized agents, flying quadcopters, are used to explore an area by mapping the distance of an unknown environment [20]. Agents have also been given roles or working with a stationary agent to explore an area. For search and rescue, agents are given a larger environment than what they can explore while staying in range so they must go out of communication range with agents being declared explorers or relays [21]. Area is shared from the explorer to the relay and then back to the command center [21]. Another case is when the agent must communicate with a computer when an obstacle is located so that the computer can determine the path to take [22]. The agents can also make a decision given multiple criteria to locate and rescue victims within a limited amount of time [23].