ترغب بنشر مسار تعليمي؟ اضغط هنا

Decentralized Dynamic Task Allocation in Swarm Robotic Systems for Disaster Response

302   0   0.0 ( 0 )
 نشر من قبل Souma Chowdhury
 تاريخ النشر 2019
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Multiple robotic systems, working together, can provide important solutions to different real-world applications (e.g., disaster response), among which task allocation problems feature prominently. Very few existing decentralized multi-robotic task allocation (MRTA) methods simultaneously offer the following capabilities: consideration of task deadlines, consideration of robot range and task completion capacity limitations, and allowing asynchronous decision-making under dynamic task spaces. To provision these capabilities, this paper presents a computationally efficient algorithm that involves novel construction and matching of bipartite graphs. Its performance is tested on a multi-UAV flood response application.

قيم البحث

اقرأ أيضاً

Decentralized swarm robotic solutions to searching for targets that emit a spatially varying signal promise task parallelism, time efficiency, and fault tolerance. It is, however, challenging for swarm algorithms to offer scalability and efficiency, while preserving mathematical insights into the exhibited behavior. A new decentralized search method (called Bayes-Swarm), founded on batch Bayesian Optimization (BO) principles, is presented here to address these challenges. Unlike swarm heuristics approaches, Bayes-Swarm decouples the knowledge generation and task planning process, thus preserving insights into the emergent behavior. Key contributions lie in: 1) modeling knowledge extraction over trajectories, unlike in BO; 2) time-adaptively balancing exploration/exploitation and using an efficient local penalization approach to account for potential interactions among different robots planned samples; and 3) presenting an asynchronous implementation of the algorithm. This algorithm is tested on case studies with bimodal and highly multimodal signal distributions. Up to 76 times better efficiency is demonstrated compared to an exhaustive search baseline. The benefits of exploitation/exploration balancing, asynchronous planning, and local penalization, and scalability with swarm size, are also demonstrated.
Swarm robotic search is concerned with searching targets in unknown environments (e.g., for search and rescue or hazard localization), using a large number of collaborating simple mobile robots. In such applications, decentralized swarm systems are t outed for their task/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, simultaneously offering computationally-efficient scalability and fundamental insights into the exhibited behavior (instead of a black-box behavior model), remains challenging under either of these two class of approaches. In this paper, we develop an important extension of the batch Bayesian search method for application to embodied swarm systems, searching in a physical 2D space. 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. Significantly superior performance, in terms of mission completion efficiency, is observed compared to exhaustive search and random walk baselines, along with favorable performance scalability with increasing swarm size.
One of the crucial problems in robotic swarm-based operation is to search and neutralize heterogeneous targets in an unknown and uncertain environment, without any communication within the swarm. Here, some targets can be neutralized by a single robo t, while others need multiple robots in a particular sequence to neutralize them. The complexity in the problem arises due to the scalability and information uncertainty, which restricts the robots awareness of the swarm and the target distribution. In this paper, this problem is addressed by proposing a novel Context-Aware Deep Q-Network (CA-DQN) framework to obtain communication free cooperation between the robots in the swarm. Each robot maintains an adaptive grid representation of the vicinity with the context information embedded into it to keep the swarm intact while searching and neutralizing the targets. The problem formulation uses a reinforcement learning framework where two Deep Q-Networks (DQNs) handle conflict and conflict-free scenarios separately. The self-play-in-based approach is used to determine the optimal policy for the DQNs. Monte-Carlo simulations and comparison studies with a state-of-the-art coalition formation algorithm are performed to verify the performance of CA-DQN with varying environmental parameters. The results show that the approach is invariant to the number of detected targets and the number of robots in the swarm. The paper also presents the real-time implementation of CA-DQN for different scenarios using ground robots in a laboratory environment to demonstrate the working of CA-DQN with low-power computing devices.
This paper addresses the task allocation problem for multi-robot systems. The main issue with the task allocation problem is inherent complexity that makes finding an optimal solution within a reasonable time almost impossible. To hand the issue, thi s paper develops a task allocation algorithm that can be decentralised by leveraging the submodularity concepts and sampling process. The theoretical analysis reveals that the proposed algorithm can provide approximation guarantee of $1/2$ for the monotone submodular case and $1/4$ for the non-monotone submodular case in average sense with polynomial time complexity. To examine the performance of the proposed algorithm and validate the theoretical analysis results, we design a task allocation problem and perform numerical simulations. The simulation results confirm that the proposed algorithm achieves solution quality, which is comparable to a state-of-the-art algorithm in the monotone case, and much better quality in the non-monotone case with significantly less computational complexity.
The focus of this paper is on solving multi-robot planning problems in continuous spaces with partial observability. Decentralized partially observable Markov decision processes (Dec-POMDPs) are general models for multi-robot coordination problems, b ut representing and solving Dec-POMDPs is often intractable for large problems. To allow for a high-level representation that is natural for multi-robot problems and scalable to large discrete and continuous problems, this paper extends the Dec-POMDP model to the decentralized partially observable semi-Markov decision process (Dec-POSMDP). The Dec-POSMDP formulation allows asynchronous decision-making by the robots, which is crucial in multi-robot domains. We also present an algorithm for solving this Dec-POSMDP which is much more scalable than previous methods since it can incorporate closed-loop belief space macro-actions in planning. These macro-actions are automatically constructed to produce robust solutions. The proposed methods performance is evaluated on a complex multi-robot package delivery problem under uncertainty, showing that our approach can naturally represent multi-robot problems and provide high-quality solutions for large-scale problems.

الأسئلة المقترحة

التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا