skip to main content


Title: An Extended Bayesian Optimization Approach to Decentralized Swarm Robotic Search
Abstract Swarm robotic search aims at searching targets using a large number of collaborating simple mobile robots, with applications to search and rescue and hazard localization. In this regard, decentralized swarm systems are touted for their coverage scalability, time efficiency, and fault tolerance. To guide the behavior of such swarm systems, two broad classes of approaches are available, namely, nature-inspired swarm heuristics and multi-robotic search methods. However, the ability to simultaneously achieve efficient scalability and provide fundamental insights into the exhibited behavior (as opposed to exhibiting a black-box behavior) remains an open problem. To address this problem, this paper extends the underlying search approach in batch-Bayesian optimization to perform search with embodied swarm agents operating in a (simulated) physical 2D arena. Key contributions lie in (1) designing an acquisition function that not only balances exploration and exploitation across the swarm but also allows modeling knowledge extraction over trajectories and (2) developing its distributed implementation to allow asynchronous task inference and path planning by the swarm robots. The resulting collective informative path planning approach is tested on target-search case studies of varying complexity, where the target produces a spatially varying (measurable) signal. Notably, superior performance, in terms of mission completion efficiency, is observed compared to exhaustive search and random walk baselines as well as a swarm optimization-based state-of-the-art method. Favorable scalability characteristics are also demonstrated.  more » « less
Award ID(s):
1927462
NSF-PAR ID:
10201755
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Journal of Computing and Information Science in Engineering
Volume:
20
Issue:
5
ISSN:
1530-9827
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Efficient path planning and communication of multi-robot systems in the case of a search and rescue operation is a critical issue facing robotics disaster relief efforts. Ensuring all the nodes of a specialized robotic search team are within range, while also covering as much area as possible to guarantee efficient response time, is the goal of this paper. We propose a specialized search-and-rescue model based on a mesh network topology of aerial and ground robots. The proposed model is based on several methods. First, each robot determines its position relative to other robots within the system, using RSSI. Packets are then communicated to other robots in the system detailing important information regarding robot system status, status of the mission, and identification number. The results demonstrate the ability to determine multi-robot navigation with RSSI, allowing low computation costs and increased search-and-rescue time efficiency. 
    more » « less
  2. This paper compares different distributed control approaches that enable a team of robots search for and track an unknown number of targets. The robots are equipped with sensors which have limited field of view (FoV) and are required to explore the environment. The team uses a distributed formulation of the Probability Hypothesis Density (PHD) filter to estimate the number and the position of the targets. The resulting target estimate is used to select the future search locations for each robot. This paper compares Lloyd’s algorithm, a traditional method for distributed search, with two typical stochastic optimization methods, Particle Swarm Optimization (PSO) and Simulated Annealing (SA). PSO and SA are traditionally used to find a single global maximum, therefore this paper describes novel formulations of PSO and SA to solve the problem of multi-target tracking. These new methods more effectively trade off between exploration and exploitation. Simulations demonstrate that the use of these stochastic optimization techniques improves coverage of the search space and reduces the error in the target estimates compared to the baseline approach. 
    more » « less
  3. Issa, R. (Ed.)
    The construction industry has traditionally been a labor-intensive industry. Typically, labor cost takes a significant portion of the total project cost. In spite of the good pay, there was a big gap recently between demand and supply in construction trades position. A survey shows that more than 80% of construction companies in the Midwest of US are facing workforce shortage and suffering in finding enough skilled trades people to hire. This workforce shortage is also nationwide or even worldwide in many places. Construction automation provides a potential solution to mitigate this problem by seeking to replace some of the demanding, repetitive, and/or dangerous construction operations with robotic automation. Currently, robots have been used in bricklaying or heavy-lifting operations in the industry, and other uses remain to be explored. In this paper, the authors proposed a feasibility breakdown structure (FBS)-based robotic system method that can be used to test the feasibility of performing target construction operations with specific robotic systems, including a top-down work breakdown structure and a bottom-up set of feasibility analysis components based on literature search and/or simulation. The proposed method was demonstrated in testing the use of a KUKA robot and a Fetch robot to perform rebar mesh construction. Results showed that the overall workflow is feasible, whereas certain limitations presented in path planning. In addition, a smooth and timely information flow from the Fetch robot sensor and computer vision-based control to the two robots for a coordinated path planning and cooperation is critical for such constructability. 
    more » « less
  4. Modular self-assembling systems typically assume that modules are present to assemble. But in sparsely observed ocean environments, modules of an aquatic modular robotic system may be separated by distances they do not have the energy to cross, and the information needed for optimal path planning is often unavailable. In this work we present a flow-based rendezvous and docking controller that allows aquatic robots in gyre-like environments to rendezvous with and dock to a target by leveraging environmental forces. This approach does not require complete knowledge of the flow, but suffices with imperfect knowledge of the flow's center and shape. We validate the performance of this control approach in both simulations and experiments relative to naive rendezvous and docking strategies, and show that energy efficiency improves as the scale of the gyre increases. 
    more » « less
  5. null (Ed.)
    Complex service robotics scenarios entail unpredictable task appearance both in space and time. This requires robots to continuously relocate and imposes a trade-off between motion costs and efficiency in task execution. In such scenarios, multi-robot systems and even swarms of robots can be exploited to service different areas in parallel. An efficient deployment needs to continuously determine the best allocation according to the actual service needs, while also taking relocation costs into account when such allocation must be modified. For large scale problems, centrally predicting optimal allocations and movement paths for each robot quickly becomes infeasible. Instead, decentralized solutions are needed that allow the robotic system to self-organize and adaptively respond to the task demands. In this paper, we propose a distributed and asynchronous approach to simultaneous task assignment and path planning for robot swarms, which combines a bio-inspired collective decision-making process for the allocation of robots to areas to be serviced, and a search-based path planning approach for the actual routing of robots towards tasks to be executed. Task allocation exploits a hierarchical representation of the workspace, supporting the robot deployment to the areas that mostly require service. We investigate four realistic environments of increasing complexity, where each task requires a robot to reach a location and work for a specific amount of time. The proposed approach improves over two different baseline algorithms in specific settings with statistical significance, while showing consistently good results overall. Moreover, the proposed solution is robust to limited communication and robot failures. 
    more » « less