Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (1): 172-178.DOI: 10.11772/j.issn.1001-9081.2015.01.0172

Previous Articles     Next Articles

Quadratic path planning algorithm based on sliding window and ant colony optimization algorithm

LAI Zhiming1,2, GUO Gongde1,2   

  1. 1. College of Mathematics and Computer Science, Fujian Normal University, Fuzhou Fujian 350007, China;
    2. Fujian Key Laboratory of Network Security and Cryptography, Fujian Normal University, Fuzhou Fujian 350007, China
  • Received:2014-08-11 Revised:2014-09-17 Online:2015-01-01 Published:2015-01-26

基于滑动窗口和蚁群优化算法的二次路径规划算法

赖智铭1,2, 郭躬德1,2   

  1. 1. 福建师范大学 数学与计算机科学学院, 福州350007;
    2. 福建师范大学 网络安全与密码技术福建省重点实验室, 福州350007
  • 通讯作者: 郭躬德
  • 作者简介:赖智铭(1988-),男,福建龙岩人,硕士研究生,主要研究方向:人工智能、数据挖掘;郭躬德(1965-),男,福建龙岩人,教授,博士生导师,主要研究方向:人工智能、数据挖掘.
  • 基金资助:

    国家自然科学基金资助项目(61070062, 61175123);福建高校产学合作科技重大项目(2010H6007).

Abstract:

A Quadratic path planning algorithm based on sliding window and Ant Colony Optimization (QACO) algorithm was put forward on the issue of weak planning ability of Ant Colony Optimization (ACO) algorithm in complex environments. The feedback strategy of the ACO based on Feedback Strategy (ACOFS) algorithm was improved, and the feedback times were reduced through the decrease of pheromone along feedback path. In the first path planning, the improved ACO algorithm was applied to make a global path planning for the grid environment. In the second path planning, the sliding windows slid along the global path. Local path in sliding windows was planned with ACO algorithm. Then the global path could be optimized by local path until target location was contained in the sliding window. The simulation experiments show that, the average planning time of QACO algorithm respectively reduces by 26.21%, 52.03% and the average length of path reduces by 47.82%, 42.28% compared with the ACO and QACO algorithms. So the QACO algorithm has a relatively strong path planning ability in complex environments.

Key words: sliding window, Ant Colony Optimization (ACO) algorithm, quadratic path planning, grid method

摘要:

针对蚁群优化(ACO)算法在复杂环境下规划能力较弱的问题,提出了一种基于滑动窗口和蚁群优化算法的二次路径规划(QACO)算法.对回退蚁群优化(ACOFS)算法的回退策略进行改进,通过降低回退路径上的信息素量,减少回退次数.第一次规划中,使用改进后的ACO算法对栅格环境进行全局路径规划;第二次规划中,滑动窗口沿着全局路径滑动,通过ACO算法规划出滑动窗口中的局部路径,并使用局部路径对全局路径进行优化,直至滑动窗口中包含目标位置.仿真实验表明:相比ACO、ACOFS算法,QACO算法的平均规划时间分别下降了26.21%、52.03%,平均路径长度下降了47.82%、42.28%,因此在复杂环境下QACO算法具有将强的路径规划能力.

关键词: 滑动窗口, 蚁群优化算法, 二次路径规划, 栅格法

CLC Number: