Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Interleaved Approach to Trait-Based Task Allocation and Scheduling
53
0
0.0
(
0
)
Added by
Glen Neville
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
To realize effective heterogeneous multi-robot teams, researchers must leverage individual robots relative strengths and coordinate their individual behaviors. Specifically, heterogeneous multi-robot systems must answer three important questions: textit{who} (task allocation), textit{when} (scheduling), and textit{how} (motion planning). While specific variants of each of these problems are known to be NP-Hard, their interdependence only exacerbates the challenges involved in solving them together. In this paper, we present a novel framework that interleaves task allocation, scheduling, and motion planning. We introduce a search-based approach for trait-based time-extended task allocation named Incremental Task Allocation Graph Search (ITAGS). In contrast to approaches that solve the three problems in sequence, ITAGSs interleaved approach enables efficient search for allocations while simultaneously satisfying scheduling constraints and accounting for the time taken to execute motion plans. To enable effective interleaving, we develop a convex combination of two search heuristics that optimizes the satisfaction of task requirements as well as the makespan of the associated schedule. We demonstrate the efficacy of ITAGS using detailed ablation studies and comparisons against two state-of-the-art algorithms in a simulated emergency response domain.
rate research
Read More
Efficient utilization of cooperating robots in the assembly of aircraft structures relies on balancing the workload of the robots and ensuring collision-free scheduling. We cast this problem as that of allocating a large number of repetitive assembly tasks, such as drilling holes and installing fasteners, among multiple robots. Such task allocation is often formulated as a Traveling Salesman Problem (TSP), which is NP-hard, implying that computing an exactly optimal solution is computationally prohibitive for real-world applications. The problem complexity is further exacerbated by intermittent robot failures necessitating real-time task reallocation. In this letter, we present an efficient method that exploits workpart geometry and problem structure to initially generate balanced and conflict-free robot schedules under nominal conditions. Subsequently, we deal with the failures by allowing the robots to first complete their nominal schedules and then employing a market-based optimizer to allocate the leftover tasks. Results show an improvement of 11.5% in schedule efficiency as compared to an optimized greedy multi-agent scheduler on a four robot system, which is especially promising for aircraft assembly processes that take many hours to complete. Moreover, the computation times are similar and small, typically hundreds of milliseconds.
We consider multi-agent transport task problems where, e.g. in a factory setting, items have to be delivered from a given start to a goal pose while the delivering robots need to avoid collisions with each other on the floor. We introduce a Task Conflict-Based Search (TCBS) Algorithm to solve the combined delivery task allocation and multi-agent path planning problem optimally. The problem is known to be NP-hard and the optimal solver cannot scale. However, we introduce it as a baseline to evaluate the sub-optimality of other approaches. We show experimental results that compare our solver with different sub-optimal ones in terms of regret.
In this paper, we consider the network power minimization problem in a downlink cloud radio access network (C-RAN), taking into account the power consumed at the baseband unit (BBU) for computation and the power consumed at the remote radio heads and fronthaul links for transmission. The power minimization problem for transmission is a fast time-scale issue whereas the power minimization problem for computation is a slow time-scale issue. Therefore, the joint network power minimization problem is a mixed time-scale problem. To tackle the time-scale challenge, we introduce large system analysis to turn the original fast time-scale problem into a slow time-scale one that only depends on the statistical channel information. In addition, we propose a bound improving branch-and-bound algorithm and a combinational algorithm to find the optimal and suboptimal solutions to the power minimization problem for computation, respectively, and propose an iterative coordinate descent algorithm to find the solutions to the power minimization problem for transmission. Finally, a distributed algorithm based on hierarchical decomposition is proposed to solve the joint network power minimization problem. In summary, this work provides a framework to investigate how execution efficiency and computing capability at BBU as well as delay constraint of tasks can affect the network power minimization problem in C-RANs.
The presence and coexistence of human operators and collaborative robots in shop-floor environments raises the need for assigning tasks to either operators or robots, or both. Depending on task characteristics, operator capabilities and the involved robot functionalities, it is of the utmost importance to design strategies allowing for the concurrent and/or sequential allocation of tasks related to object manipulation and assembly. In this paper, we extend the textsc{FlexHRC} framework presented in cite{darvish2018flexible} to allow a human operator to interact with multiple, heterogeneous robots at the same time in order to jointly carry out a given task. The extended textsc{FlexHRC} framework leverages a concurrent and sequential task representation framework to allocate tasks to either operators or robots as part of a dynamic collaboration process. In particular, we focus on a use case related to the inspection of product defects, which involves a human operator, a dual-arm Baxter manipulator from Rethink Robotics and a Kuka youBot mobile manipulator.
With the development of federated learning (FL), mobile devices (MDs) are able to train their local models with private data and sends them to a central server for aggregation, thereby preventing sensitive raw data leakage. In this paper, we aim to improve the training performance of FL systems in the context of wireless channels and stochastic energy arrivals of MDs. To this purpose, we dynamically optimize MDs transmission power and training task scheduling. We first model this dynamic programming problem as a constrained Markov decision process (CMDP). Due to high dimensions rooted from our CMDP problem, we propose online stochastic learning methods to simplify the CMDP and design online algorithms to obtain an efficient policy for all MDs. Since there are long-term constraints in our CMDP, we utilize Lagrange multipliers approach to tackle this issue. Furthermore, we prove the convergence of the proposed online stochastic learning algorithm. Numerical results indicate that the proposed algorithms can achieve better performance than the benchmark algorithms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
