Event- and time-triggered dynamic task assignments for multiple vehicles

Bai, Xiaoshan; Cao, Ming; Yan, Weisheng · 2020 · Crossref

DOI: 10.1007/s10514-020-09912-1

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the dynamic task assignment problem for multiple dispersed vehicles tasked with visiting a set of target locations. The problem is motivated by applications in logistics, terrain mapping, and environmental monitoring, where some target locations are known initially while others are generated randomly during a finite time horizon. The objective is to visit all targets while minimizing the total travel time of the vehicle fleet. The authors identify a gap in existing literature, which largely focuses on static assignments or assumes all targets are known, by investigating when and how to dynamically reassign targets in response to new arrivals. The study proposes and compares two categories of dynamic assignment strategies: event-triggered and time-triggered. Event-triggered algorithms reassign tasks immediately upon the generation of a new target, whereas time-triggered algorithms perform reassignments at fixed intervals. For each category, the authors develop algorithms based on two underlying static assignment methods: Extended Voronoi Clustering with Marginal Cost (EVM) and Marginal Cost (MC). These are further divided into two mechanisms: inserting new targets into existing paths or reassigning all currently unvisited targets. This results in eight specific dynamic algorithms (e.g., EEVME, EMCE, TEVME, TMCA), which are benchmarked against a standard greedy algorithm. Extensive Monte Carlo simulations were conducted to evaluate performance. The experimental setup involved five vehicles and 30 initial targets distributed in a square area, with new targets arriving at varying rates. Solution quality was measured by the ratio of total travel time to the lower bound provided by the Minimum Spanning Tree (MST) of the target-vehicle graph. The results demonstrate that event-triggered algorithms consistently outperform time-triggered algorithms in terms of solution quality across different target arrival rates. Specifically, algorithms that reassign all unvisited targets (such as EEVMA and EMCA) generally yield better performance than those that only insert new targets into existing paths, though they may incur higher computational costs. The greedy algorithm served as a baseline, showing inferior performance compared to the proposed clustering-based methods. The significance of this work lies in providing a comparative framework for dynamic task assignment in multi-vehicle systems. The findings suggest that event-triggered mechanisms are more effective for minimizing travel time in dynamic environments, particularly when the arrival rate of new targets is moderate to high. By establishing that immediate reassignment yields better results than periodic updates, the paper offers practical guidance for designing real-time control systems for autonomous fleets. The study also highlights the trade-off between solution optimality and computational effort, noting that while comprehensive reassignment improves performance, it requires more processing power.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• driverless ads