<p>The Multi-vehicle Path Planning (MVPP) problem involves simultaneously solving multiple vehicle path planning tasks within a transportation network that may share similarities in space, tasks, or constraints. Existing methods for the MVPP problem mainly depend on single-task optimization approaches like the traditional ant colony optimization, which typically use either centralized pooling for collaborative optimization or sequential independent optimization of each vehicle’s path. However, as the size of the transportation network expands, single-task optimization faces increasing challenges in solving the MVPP problem. Multi-task optimization is an emerging and promising field that aims to enhance the performance of optimization algorithms through multi-task learning and knowledge sharing, thereby positively impacting various applications like the MVPP. This paper proposes a Multi-Task Ant Colony Optimization (MTACO) method, which allows multiple ant colonies to explore their respective pheromone matrices, thereby facilitating implicit knowledge sharing. In MTACO, each ant colony is responsible for a single vehicle path planning task, and knowledge transfer between tasks is achieved through an archive-based initialization strategy and a probabilistic knowledge transfer strategy, which leverage similarities between tasks to improve overall optimization performance. Furthermore, a similar-task association strategy is introduced to assess the correlation between different vehicle path planning tasks, enabling more effective sharing of valuable search information. Experimental results demonstrate that MTACO outperforms several state-of-the-art methods in various test instances, especially when dealing with multiple vehicle path planning tasks with similarities, exhibiting significant advantages and delivering globally optimal or near-optimal path solutions for all tasks even in large-scale networks.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Multi-task Ant Colony Optimization for Multi-vehicle Path Planning

  • Wei-Li Liu,
  • Zhenjian Yu,
  • Zhixing Huang,
  • Jinghui Zhong,
  • Xu Lu,
  • Zhiyong Lin,
  • Huimin Zhao

摘要

The Multi-vehicle Path Planning (MVPP) problem involves simultaneously solving multiple vehicle path planning tasks within a transportation network that may share similarities in space, tasks, or constraints. Existing methods for the MVPP problem mainly depend on single-task optimization approaches like the traditional ant colony optimization, which typically use either centralized pooling for collaborative optimization or sequential independent optimization of each vehicle’s path. However, as the size of the transportation network expands, single-task optimization faces increasing challenges in solving the MVPP problem. Multi-task optimization is an emerging and promising field that aims to enhance the performance of optimization algorithms through multi-task learning and knowledge sharing, thereby positively impacting various applications like the MVPP. This paper proposes a Multi-Task Ant Colony Optimization (MTACO) method, which allows multiple ant colonies to explore their respective pheromone matrices, thereby facilitating implicit knowledge sharing. In MTACO, each ant colony is responsible for a single vehicle path planning task, and knowledge transfer between tasks is achieved through an archive-based initialization strategy and a probabilistic knowledge transfer strategy, which leverage similarities between tasks to improve overall optimization performance. Furthermore, a similar-task association strategy is introduced to assess the correlation between different vehicle path planning tasks, enabling more effective sharing of valuable search information. Experimental results demonstrate that MTACO outperforms several state-of-the-art methods in various test instances, especially when dealing with multiple vehicle path planning tasks with similarities, exhibiting significant advantages and delivering globally optimal or near-optimal path solutions for all tasks even in large-scale networks.