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, more » 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. « less
Award ID(s):
Publication Date:
Journal Name:
Journal of Computing and Information Science in Engineering
Sponsoring Org:
National Science Foundation
More Like this
  1. 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 aremore »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.« less
  2. 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 aremore »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.« less
  3. A Task Decomposition method for iterative learning Model Predictive Control (TDMPC) for linear time-varying systems is presented. We consider the availability of state- input trajectories which solve an original task T1, and design a feasible MPC policy for a new task, T2, using stored data from T1. Our approach applies to tasks T2 which are composed of subtasks contained in T1. In this paper we formally define the task decomposition problem, and provide a feasibility proof for the resulting policy. The proposed algorithm reduces the computational burden for linear time-varying systems with piecewise convex constraints. Simulation results demonstrate the improvedmore »efficiency of the proposed method on a robotic path-planning task.« less
  4. To mitigate the long-term spectrum crunch problem, the FCC recently opened up the 6 GHz frequency band for unlicensed use. However, the existing spectrum sharing strategies cannot support the operation of access points in moving vehicles such as cars and UAVs. This is primarily because of the directionality-based spectrum sharing among the incumbent systems in this band and the high mobility of the moving vehicles, which together make it challenging to control the cross-system interference. In this paper we propose SwarmShare, a mobility-resilient spectrum sharing framework for swarm UAV networking in the 6 GHz band. We first present a mathematicalmore »formulation of the SwarmShare problem, where the objective is to maximize the spectral efficiency of the UAV network by jointly controlling the flight and transmission power of the UAVs and their association with the ground users, under the interference constraints of the incumbent system. We find that there are no closed-form mathematical models that can be used characterize the statistical behaviors of the aggregate interference from the UAVs to the incumbent system. Then we propose a data-driven three-phase spectrum sharing approach, including Initial Power Enforcement, Offline-dataset Guided Online Power Adaptation, and Reinforcement Learning-based UAV Optimization. We validate the effectiveness of SwarmShare through an extensive simulation campaign. Results indicate that, based on SwarmShare, the aggregate interference from the UAVs to the incumbent system can be effectively controlled below the target level without requiring the real-time cross-system channel state information. The mobility resilience of SwarmShare is also validated in coexisting networks with no precise UAV location information.« less
  5. Multi-Agent Path Finding (MAPF) problems are traditionally solved in a centralized manner. There are works focusing on completeness, optimality, performance, or a tradeoff between them. However, there are only a few works based on spatial distribution. In this paper, we introduce ros-dmapf, a distributed MAPF solver. It consists of multiple MAPF sub-solvers, which---besides solving their assigned sub-problems---interact with each other to solve a given MAPF problem. In the current implementation, the sub-solvers are answer set planning systems for multiple agents, and are created based on spatial distribution of the problem. Interactions between components of ros-dmapf are facilitated by the Robotmore »Operating System (ROS). The highlights of ros-dmapf are its scalability and a high degree of parallelism. We empirically evaluate ros-dmapf using the move-only domain of the asprilo system and results suggest that ros-dmapf scales up well. For instance, ros-dmapf gives a solution of length around 600 for a MAPF problem with 2000 robots in randomly generated 100×100 obstacle-free maps---a problem beyond the capability of a single sub-solver---within 7 minutes on a consumer laptop. We also evaluate ros-dmapf against some other MAPF solvers and results show that the system performs well. We also discuss possible improvements for future work.« less