skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.


This content will become publicly available on September 1, 2025

Title: Learning to Allocate Time-Bound and Dynamic Tasks to Multiple Robots Using Covariant Attention Neural Networks
Abstract

In various applications of multi-robotics in disaster response, warehouse management, and manufacturing, tasks that are known a priori and tasks added during run time need to be assigned efficiently and without conflicts to robots in the team. This multi-robot task allocation (MRTA) process presents itself as a combinatorial optimization (CO) problem that is usually challenging to be solved in meaningful timescales using typical (mixed)integer (non)linear programming tools. Building on a growing body of work in using graph reinforcement learning to learn search heuristics for such complex CO problems, this paper presents a new graph neural network architecture called the covariant attention mechanism (CAM). CAM can not only generalize but also scale to larger problems than that encountered in training, and handle dynamic tasks. This architecture combines the concept of covariant compositional networks used here to embed the local structures in task graphs, with a context module that encodes the robots’ states. The encoded information is passed onto a decoder designed using multi-head attention mechanism. When applied to a class of MRTA problems with time deadlines, robot ferry range constraints, and multi-trip settings, CAM surpasses a state-of-the-art graph learning approach based on the attention mechanism, as well as a feasible random-walk baseline across various generalizability and scalability tests. Performance of CAM is also found to be at par with a high-performing non-learning baseline called BiG-MRTA, while noting up to a 70-fold improvement in decision-making efficiency over this baseline.

 
more » « less
Award ID(s):
2048020
PAR ID:
10538894
Author(s) / Creator(s):
;
Publisher / Repository:
ASME
Date Published:
Journal Name:
Journal of Computing and Information Science in Engineering
Volume:
24
Issue:
9
ISSN:
1530-9827
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    This paper introduces a new graph neural network architecture for learning solutions of Capacitated Vehicle Routing Problems (CVRP) as policies over graphs. CVRP serves as an important benchmark for a wide range of combinatorial planning problems, which can be adapted to manufacturing, robotics and fleet planning applications. Here, the specific aim is to demonstrate the significant real-time executability and (beyond training) scalability advantages of the new graph learning approach over existing solution methods. While partly drawing motivation from recent graph learning methods that learn to solve CO problems such as multi-Traveling Salesman Problem (mTSP) and VRP, the proposed neural architecture presents a novel encoder-decoder architecture. Here the encoder is based on Capsule networks, which enables better representation of local and global information with permutation invariant node embeddings; and the decoder is based on the Multi-head attention (MHA) mechanism allowing sequential decisions. This architecture is trained using a policy gradient Reinforcement Learning process. The performance of our approach is favorably compared with state-of-the-art learning and non-learning methods for a benchmark suite of Capacitated-VRP (CVRP) problems. A further study on the CVRP with demand uncertainties is conducted to explore how this Capsule-Attention Mechanism architecture can be extended to handle real-world uncertainties by embedding them through the encoder.

     
    more » « less
  2. We consider multi-robot service scenarios, where tasks appear at any time and in any location of the working area. A solution to such a service task problem requires finding a suitable task assignment and a collision-free trajectory for each robot of a multi-robot team. In cluttered environments, such as indoor spaces with hallways, those two problems are tightly coupled. We propose a decentralized algorithm for simultaneously solving both problems, called Hierarchical Task Assignment and Path Finding (HTAPF). HTAPF extends a previous bio-inspired Multi-Robot Task Allocation (MRTA) framework [1]. In this work, task allocation is performed on an arbitrarily deep hierarchy of work areas and is tightly coupled with a fully distributed version of the priority-based planning paradigm [12], using only broadcast communication. Specifically, priorities are assigned implicitly by the order in which data is received from nearby robots. No token passing procedure or specific schedule is in place ensuring robust execution also in the presence of limited probabilistic communication and robot failures. 
    more » « less
  3. null (Ed.)
    Surgical robots for laparoscopy consist of several patient side slave manipulators that are controlled via surgeon operated master telemanipulators. Commercial surgical robots do not perform any sub-tasks - even of repetitive or noninvasive nature - autonomously or provide intelligent assistance. While this is primarily due to safety and regulatory reasons, the state of such automation intelligence also lacks the reliability and robustness for use in high-risk applications. Recent developments in continuous control using Artificial Intelligence and Reinforcement Learning have prompted growing research interest in automating mundane sub-tasks. To build on this, we present an inspired Asynchronous Framework which incorporates realtime dynamic simulation - manipulable with the masters of a surgical robot and various other input devices - and interfaces with learning agents to train and potentially allow for the execution of shared sub-tasks. The scope of this framework is generic to cater to various surgical (as well as non-surgical) training and control applications. This scope is demonstrated by examples of multi-user and multi-manual applications which allow for realistic interactions by incorporating distributed control, shared task allocation and a well-defined communication pipe-line for learning agents. These examples are discussed in conjunction with the design philosophy, specifications, system-architecture and metrics of the Asynchronous Framework and the accompanying Simulator. We show the stability of Simulator while achieving real-time dynamic simulation and interfacing with several haptic input devices and a training agent at the same time. 
    more » « less
  4. 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
  5. Abstract

    Collaborative robots must simultaneously be safe enough to operate in close proximity to human operators and powerful enough to assist users in industrial tasks such as lifting heavy equipment. The requirement for safety necessitates that collaborative robots are designed with low-powered actuators. However, some industrial tasks may require the robot to have high payload capacity and/or long reach. For collaborative robot designs to be successful, they must find ways of addressing these conflicting design requirements. One promising strategy for navigating this tradeoff is through the use of static balancing mechanisms to offset the robot’s self-weight, thus enabling the selection of low-powered actuators. In this paper, we introduce a novel, two degrees-of-freedom static balancing mechanism based on spring-loaded, wire-wrapped cams. We also present an optimization-based cam design method that guarantees the cams stay convex, ensures the springs stay below their extensions limits, and minimizes sensitivity to unmodeled deviations from the nominal spring constant. Additionally, we present a model of the effect of friction between the wire and the cam. Lastly, we show experimentally that the torque generated by the cam mechanism matches the torque predicted in our modeling approach. Our results also suggest that the effects of wire-cam friction are significant for non-circular cams.

     
    more » « less