HMR-ODTA: Online Diverse Task Allocation for a Team of Heterogeneous Mobile Robots

Ashish Verma, Avinash Gautam, Tanishq Duhan, V. S. Shekhawat, Sudeept Mohan · 2025

Read HMR-ODTA: Online Diverse Task Allocation for a Team of Heterogeneous Mobile Robots by Ashish Verma, Avinash Gautam, Tanishq Duhan, V. S. Shekhawat, Sudeept Mohan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08419.txt.

Introduction

Ashish Verma and co-authors assign live fetch-and-drop jobs to a mixed robot team. In wards and shops, calls land on the fly with hard due times, and each robot can take unlike jobs. Old plans crack when calls shift mid-run. Their 2025 frame deals jobs to the team with no hub, and can re-deal them as delays bloom.

Late fees and done shares form the twin aims. Mock runs span small sets to large ones. Late fees fall by near two thirds on small sets in their runs. Gains hold, at a less rate, on big sets in the part of the sums shown. The hub-free form can grow with fleet size. Such plans fit ward bots that haul meds and meals on call.

Catalog record

CREATORAshish Verma, Avinash Gautam, Tanishq Duhan, V. S. Shekhawat, Sudeept Mohan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-08419

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

HMR-ODTA: Online Diverse Task Allocation for a Team of Heterogeneous Mobile Robots Ashish Verma, Avinash Gautam, Tanishq Duhan, V. S. Shekhawat, Sudeept Mohan Abstract Coordinating time-sensitive deliveries in environments like hospitals poses a complex challenge, particularly when managing multiple online pickup and delivery requests within strict time windows using a team of heterogeneous robots. Traditional approaches fail to address dynamic rescheduling or diverse service requirements, typically restricting robots to single-task types. This paper tackles the Multi-Pickup and Delivery Problem with Time Windows (MPDPTW), where autonomous mobile robots are capable of handling varied service requests. The objective is to minimize late delivery penalties while maximizing task completion rates. To achieve this, we propose a novel framework leveraging a heterogeneous robot team and an efficient dynamic scheduling algorithm that supports dynamic task rescheduling. Users submit requests with specific time constraints, and our decentralized algorithm—Heterogeneous Mobile Robots Online Diverse Task Allocation (HMR-ODTA)—optimizes task assignments to ensure timely service while addressing delays or task rejections. Extensive simulations validate the algorithm’s effectiveness. For smaller task sets (40–160 tasks), penalties were reduced by nearly 63%, while for larger sets (160–280 tasks), penalties decreased by approximately 50%. These results highlight the algorithm’s effectiveness in improving task scheduling and coordination in multi-robot systems, offering a robust solution for enhancing delivery performance in structured, time-critical environments. keywords Multi-robot system, Online Multi-Robot Task Allocation (MRTA), Multi-Pickup and Delivery Problem, Temporal Constraints 1 Introduction Multi-robot systems (MRS) have gained popularity due to their ability to perform complex tasks more efficiently than a single robot Khamis et al. 2015 . MRS involves task distribution and parallel work toward a shared objective, using communication for coordination, which enhances efficiency and reduces task completion time Vail and Veloso 2003 . However, MRS coordination presents challenges due to multiple non-trivial sub-problems such as task decomposition, multi-robot task allocation (MRTA), monitoring task execution progress, and termination detection. MRTA, which is NP-Hard Gerkey and Matarić 2004 , focuses on collaborative task execution, such as in crucial areas like warehouse automation Sharma and Doriya 2021 , terrain coverage Gautam et al. 2017 ; Gautam et al. 2021 , exploration Soni et al. 2022 , and search and rescue operations Khairnar et al. 2023 . MRTA problem is one of the most challenging issues in Multi-Robot Systems (MRS), particularly when dealing with heterogeneous robots equipped with diverse sensors and actuators. These robots must optimally execute various tasks, each with distinct requirements and constraints Msala et al. 2019 . This problem can be viewed as an optimal assignment problem, where the goal is to allocate a set of tasks to a group of robots in a way that maximizes the overall performance of the system. For the environments such as warehouses, hospitals, and office buildings often require the delivery of numerous items, presenting complex challenges that are commonly framed as Pickup and Delivery Problem (PDP). In this paper, we consider a real-world environment like a hospital building. In a hospital building, a team of heterogeneous robots is deployed to fulfill online incoming service requests from various users, such as doctors, wardens, and patients. Service requests are submitted via handheld devices or a web interface, with specified time constraints, and are stored in a global queue. Service requests include supply delivery, telemedicine, monitoring, patient assistance, transportation, logistics, and cleaning. In contrast to the Temporal Logic Task Allocation in heterogeneous multi-robot systems’ method addressed in Luo and Zavlanos 2022 , which relies on centralized control and pre-specified task schedules, the proposed approach in this paper i.e., HMR-ODTA dynamically reallocates tasks through an auction-based mechanism. This ensures that even when tasks arrive unpredictably, they can be effectively handled without violating time constraints . Limitations of the State-of-the-Art: A recent review paper Chakraa et al. 2023 highlights critical limitations in the field of dynamic task allocation, particularly in online and iterative methods for handling newly arriving tasks. These limitations stem from the inherent complexity of defining a cost function that can operate effectively in real-time under dynamic conditions. The challenge intensifies when task execution must adhere to strict temporal constraints, such as deadlines or specific time slots. Addressing this gap, this paper introduces a novel approach viz., Online Diverse Task Allocation for a Team of Heterogeneous Autonomous Mobile Robots (HMR-ODTA). Using HMR-ODTA a team of heterogeneous autonomous mobile robots is deployed to respond to service requests that arrive iteratively and unpredictably. Each service request is associated with a deadline, with some tasks becoming infeasible post-deadline and others incurring penalties if delayed. The proposed approach enables efficient task allocation and execution in real-time, accommodating both hard and soft temporal constraints. Major contributions of the paper: The major contributions of the paper are as follows: • The proposed approach utilizes a more adaptive strategy by employing a Simple Temporal Network (STN) Dechter et al. 1991 framework to evaluate the availability of robots within the specified time interval, defined as the period between the service request’s arrival time and its deadline. This method effectively addresses temporal constraints while incorporating essential factors—such as remaining energy, current load-carrying capacity, speed, and robot efficiency based on the type of service request—to optimize system performance. • HMR-ODTA also incorporated an adaptive task rescheduling mechanism within a robot’s schedule to handle delays or unforeseen tasks, ensuring minimal disruption and timely completion of service requests, which distinguishes it from recent approaches Wang et al. 2023 ; Martin et al. 2021 . Moreover, it accounts for the types and number of service requests that can be assigned to each robot and dynamically adjusts task allocations to maximize the efficiency and utilization of heterogeneous robot teams. • The main objective of HMR-ODTA is to maximize the number of successfully completed service requests while minimizing associated penalties. By incorporating these considerations into the STN framework, the system efficiently balances trade-offs among energy consumption, the variety of service requests each robot can handle, and the need for dynamic rescheduling. • Extensive simulations using the ROS-based Gazebo simulator ROS.org have been conducted to establish the efficacy of the proposed approach. Finally, two SOTA approaches, i.e., (a) Effective and Efficient Performance Impact Wang et al. 2023 (b) Multi-robot task allocation using Genetic Algorithm (GA-MR) Martin et al. 2021 are re-implemented for heterogeneous autonomous mobile robots for online PDP to be compared with the proposed HMR-ODTA algorithm. The proposed approach outperforms these SOTA approaches. The following sections of this paper are organized as follows: Section 2 provides an overview of the related work about the task assignment problem. Section 3 describes the preliminaries of the proposed approach and symbols. Section 4 delves into the formulation of the heterogeneous multi-robot service request assignment and execution problem. Section 5 outlines the proposed decentralized auction algorithm. Section 6 provides insights into the configuration of the simulation environment. Section 7 presents the results followed by the conclusions in Section 8 . 2 Related Work Over the past decades, task delivery to customers has faced significant challenges due to the rise of e-commerce Morganti et al. 2014 . Some environments, like warehouses, hospitals, and office buildings, require the delivery of numerous items. These challenges can be summarized as pickup and delivery problems (PDP), a type of vehicle routing problem (VRP) where items need to be

Read the complete text