Improving Multi-Agent Exploration Efficiency Through Perimeter Analysis
In the following research, collaboration between multiple robotic devices is used to efficiently explore and construct a map of an unknown structure. In order to most efficiently split up the task of exploration, various search algorithms are considered which use prior search experience to avoid redundancy and maintain stability. Different algorithms apply to different locations, such as hallways, rooms, or the outdoors. If a robot can understand its current environment, the efficiency of operating in that environment can increase. Simulations apply varying reward and cost estimates to different location types in an effort to find the most efficient search allocation method.
Introduction and Background
In any computerized exploration of an unknown environment, a robot must make decisions on the fly as it discovers new information. Using multiple robots, or teams of robots, can greatly increase search speed through division of labor and exploration of different areas simultaneously. This improved efficiency comes at a cost. Aside from monetary cost increases, multiple robots carry the risk of collision when operating in the same environment.
Proposed Algorithm Concept
This proposal assigns a high priority for gathering outdoor space data. Whether searching the outside or acquiring data from satellite or aerial photos, paying attention to the perimeter of a structure will prove especially helpful for a search team. Because structures occupy 3D space it is logical to conclude that all space within a building must be contained within the confines of the buildings exterior walls, the exception being underground areas like a basement. This algorithm tries to aid robotic searches by acquiring as much data as possible before the search starts. The presence of a basement in a building will increase search time, but the hope is that this algorithm will still improve the search efficiency to some degree for the above ground portion of the structure. If a team of robots can acquire information about a buildings exterior, the entire system of robots has a significant advantage over systems that are only aware of previously mapped interior spaces. Knowing the boundaries of a building transmits key traits about the environment to a team much quicker than exclusively indoor searches. Size, number of stories, and general shape can be estimated easily giving task allocation algorithms a much better estimate, thus improving efficiency.
The entire paper is available for download in PDF format.