Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMixed-Integer Linear Programming Models for Multi-Robot Non-Adversarial Search
111
0
0.0
(
0
)
Added by
Beatriz Asfora
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this letter, we consider the Multi-Robot Efficient Search Path Planning (MESPP) problem, where a team of robots is deployed in a graph-represented environment to capture a moving target within a given deadline. We prove this problem to be NP-hard, and present the first set of Mixed-Integer Linear Programming (MILP) models to tackle the MESPP problem. Our models are the first to encompass multiple searchers, arbitrary capture ranges, and false negatives simultaneously. While state-of-the-art algorithms for MESPP are based on simple path enumeration, the adoption of MILP as a planning paradigm allows to leverage the powerful techniques of modern solvers, yielding better computational performance and, as a consequence, longer planning horizons. The models are designed for computing optimal solutions offline, but can be easily adapted for a distributed online approach. Our simulations show that it is possible to achieve 98% decrease in computational time relative to the previous state-of-the-art. We also show that the distributed approach performs nearly as well as the centralized, within 6% in the settings studied in this letter, with the advantage of requiring significant less time - an important consideration in practical search missions.
rate research
Read More
In this paper, a mixed-integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, graph abstractions for resource-constrained agents is presented. The formulation leverages concepts from information-theoretic signal compression, specifically the information bottleneck (IB) method, to pose a graph abstraction problem as an optimal encoder search over the space of multi-resolution trees. The abstractions emerge in a task-relevant manner as a function of agent information-processing constraints, and are not provided to the system a priori. We detail our formulation and show how the problem can be realized as an integer linear program. A non-trivial numerical example is presented to demonstrate the utility in employing our approach to obtain hierarchical tree abstractions for resource-limited agents.
We study optimal Multi-robot Path Planning (MPP) on graphs, in order to improve the efficiency of multi-robot system (MRS) in the warehouse-like environment. We propose a novel algorithm, OMRPP (One-way Multi-robot Path Planning) based on Integer programming (IP) method. We focus on reducing the cost caused by a set of robots moving from their initial configuration to goal configuration in the warehouse-like environment. The novelty of this work includes: (1) proposing a topological map extraction based on the property of warehouse-like environment to reduce the scale of constructed IP model; (2) proposing one-way passage constraint to prevent the robots from having unsolvable collisions in the passage. (3) developing a heuristic architecture that IP model can always have feasible initial solution to ensure its solvability. Numerous simulations demonstrate the efficiency and performance of the proposed algorithm.
Autonomous or teleoperated robots have been playing increasingly important roles in civil applications in recent years. Across the different civil domains where robots can support human operators, one of the areas where they can have more impact is in search and rescue (SAR) operations. In particular, multi-robot systems have the potential to significantly improve the efficiency of SAR personnel with faster search of victims, initial assessment and mapping of the environment, real-time monitoring and surveillance of SAR operations, or establishing emergency communication networks, among other possibilities. SAR operations encompass a wide variety of environments and situations, and therefore heterogeneous and collaborative multi-robot systems can provide the most advantages. In this paper, we review and analyze the existing approaches to multi-robot SAR support, from an algorithmic perspective and putting an emphasis on the methods enabling collaboration among the robots as well as advanced perception through machine vision and multi-agent active perception. Furthermore, we put these algorithms in the context of the different challenges and constraints that various types of robots (ground, aerial, surface or underwater) encounter in different SAR environments (maritime, urban, wilderness or other post-disaster scenarios). This is, to the best of our knowledge, the first review considering heterogeneous SAR robots across different environments, while giving two complimentary points of view: control mechanisms and machine perception. Based on our review of the state-of-the-art, we discuss the main open research questions, and outline our insights on the current approaches that have potential to improve the real-world performance of multi-robot SAR systems.
Mixed-integer convex programming (MICP) has seen significant algorithmic and hardware improvements with several orders of magnitude solve time speedups compared to 25 years ago. Despite these advances, MICP has been rarely applied to real-world robotic control because the solution times are still too slow for online applications. In this work, we extend the machine learning optimizer (MLOPT) framework to solve MICPs arising in robotics at very high speed. MLOPT encodes the combinatorial part of the optimal solution into a strategy. Using data collected from offline problem solutions, we train a multiclass classifier to predict the optimal strategy given problem-specific parameters such as states or obstacles. Compared to previous approaches, we use task-specific strategies and prune redundant ones to significantly reduce the number of classes the predictor has to select from, thereby greatly improving scalability. Given the predicted strategy, the control task becomes a small convex optimization problem that we can solve in milliseconds. Numerical experiments on a cart-pole system with walls, a free-flying space robot and task-oriented grasps show that our method provides not only 1 to 2 orders of magnitude speedups compared to state-of-the-art solvers but also performance close to the globally optimal MICP solution.
We propose a dual dynamic integer programming (DDIP) framework for solving multi-scale mixed-integer model predictive control (MPC) problems. Such problems arise in applications that involve long horizons and/or fine temporal discretizations as well as mixed-integer states and controls (e.g., scheduling logic and discrete actuators). The approach uses a nested cutting-plane scheme that performs forward and backward sweeps along the time horizon to adaptively approximate cost-to-go functions. The DDIP scheme proposed can handle general MPC formulations with mixed-integer controls and states and can perform forward-backward sweeps over block time partitions. We demonstrate the performance of the proposed scheme by solving mixed-integer MPC problems that arise in the scheduling of central heating, ventilation, and air-conditioning (HVAC) plants. We show that the proposed scheme is scalable and dramatically outperforms state-of-the-art mixed-integer solvers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
