Ting Huang

Efficient and safe path planning for multiple autonomous agents, such as unmanned aerial vehicles (UAVs), is essential in many real-world applications. The objective is to coordinate these agents to cover a target area with minimal cost. However, most existing multi-agent coverage path planning (MACPP) methods rely on purely spatial planning and neglect spatio-temporal interactions among agents, which often result in unsafe paths and a high risk of inter-agent collisions during execution. To address this challenge, we propose a new problem formulation, termed collision-aware MACPP (CaMACPP), which incorporates both spatial coverage efficiency and collision avoidance. To solve this problem, we introduce an efficient multi-agent evolutionary algorithm to minimize costs while avoiding collisions. The algorithm first introduces a trapezoidal decomposition strategy to partition complex environments into convex subareas. Then, a cooperative evolutionary algorithm is designed to optimize the inter-area visiting orders for multiple agents and the intra-area coverage modes assigned to each agent. Next, a spatio-temporal collision avoidance mechanism is incorporated to detect and resolve conflicts between agent paths. The proposed algorithm is extensively evaluated against the state-of-the-art MACPP methods to demonstrate its effectiveness in generating collision-free paths with minimal total cost. The results show that it achieves zero collisions in all tested scenarios, reduces the average path length by 15.9%, and decreases coverage overlap by 58.1%.

Surrogate-assisted Evolutionary Algorithms~(SAEAs) have shown promising robustness in solving expensive optimization problems. A key aspect that impacts SAEAs' effectiveness is surrogate model selection, which in existing works is predominantly decided by human developer. Such human-made design choice introduces strong bias into SAEAs and may hurt their expected performance on out-of-scope tasks. In this paper, we propose a reinforcement learning-assisted ensemble framework, termed as SEEMOO, which is capable of scheduling different surrogate models within a single optimization process, hence boosting the overall optimization performance in a cooperative paradigm. Specifically, we focus on expensive multi-objective optimization problems, where multiple objective functions shape a compositional landscape and hence challenge surrogate selection. SEEMOO comprises following core designs: 1) A pre-collected model pool that maintains different surrogate models; 2) An attention-based state-extractor supports universal optimization state representation of problems with varied objective numbers; 3) a deep Q-network serves as dynamic surrogate selector: Given the optimization state, it selects desired surrogate model for current-step evaluation. SEEMOO is trained to maximize the overall optimization performance under a training problem distribution. Extensive benchmark results demonstrate SEEMOO's surrogate ensemble paradigm boosts the optimization performance of single-surrogate baselines. Further ablation studies underscore the importance of SEEMOO's design components.

Multi-Agent Path Finding (MAPF) aims at finding a set of conflict-free and cost-optimal paths for agents from pickup to delivery locations. Most existing MAPF research focus on exhaustively search for path set for the agents with conflict-free paths, which often results in high computational costs. In this letter, we aim to accelerate the path-finding process by considering the distribution of pickup-delivery pairs and leveraging task similarity. We propose TaskSimLF, a task-similarity based leader-follower path finding method. Specifically, the algorithm first employs an adaptive clustering of tasks to group them based on spatial similarity. For each group, we generate the representative leader’s path by maximizing the spatial separation of inter-group and minimizing spatiotemporal overlap. The agents within each group, referred to as followers, find their paths by following the leader's trajectory, using topological features of the leader's path to reduce intra-group conflicts. Experimental results demonstrate that our proposed algorithm shows superior performance while significantly improves runtime efficiency with fewer node expansion in different map scenarios.

The limited range of electric vehicles (EVs) necessitates frequent charging during long-distance travel, posing significant challenges in routing. Unlike traditional vehicles, EVs face additional constraints such as extended charging times and potential queues at charging stations (CSs), which can substantially increase travel time. Addressing these complexities is critical for enhancing travel efficiency and user experience. This article presents MultiCRPlanner, a novel system that provides multiple optimized solutions tailored to real-world scenarios. Specifically, we introduce a comprehensive long-distance EV charge-route planning (LD-CRP) model, which is built upon a bi-layer network to balance practical details with routing efficiency. To enable users to flexibly adjust and select the most suitable plan based on their specific requirements, we develop a clustering-based multi-solution genetic algorithm (GA). This clustering scheme enables the algorithm to identify a set of solutions with both high quality and diversity. In addition, our algorithm is equipped with a few tailored crossover and mutation operators to enhance problem-solving efficiency. We validate the effectiveness of MultiCRPlanner through experiments on two real-world datasets, demonstrating its superiority over existing algorithms.

Multi-Agent Path Finding (MAPF) focuses on navigating agents along cost-efficient and conflict-free paths. This letter investigates a challenging and practical MAPF variant, namely Robust Lifelong MAPF (RLMAPF), where agents sequentially receive tasks and effectively deal with uncertainties. In this letter, we first establish a comprehensive RLMAPF problem model with a novel conflict category methodology: active and passive conflicts. Based on this model, we introduce a decentralized robust path finding algorithm that comprises two fundamental components: the robust path finding and decentralized path execution. The first component focuses on robust MAPF by integrating a conflict prediction oracle, a rolling window for conflict detection, and active conflict resolution. Based on the robust path without active conflicts provided by the planning phase, the path executor aims at passive conflict avoidance in a decentralized method. The empirical evaluation of the proposed algorithm against the state-of-the-art MAPF methods reveals its superiority. Through extensive simulations, we demonstrate that the proposed algorithm has a low replanning frequency and high robustness, maintaining a robustness index of 0.95 in most uncertain environments—at least 20% higher than the state-of-the-art comparison MAPF algorithms.