FPGA implementation of improved ant colony optimization algorithm based on pheromone diffusion mechanism for path planning

Chen-Chien James Hsu, Wei Yen Wang, Yi Hsing Chien, Ru Yu Hou

Research output: Contribution to journalArticle

Abstract

An improved ant colony optimization (ACO) algorithm is proposed in this paper for improving the accuracy of path planning. The main idea of this paper is to avoid local minima by continuously tuning a setting parameter and the establishment of novel mechanisms by means of partial pheromone updating and opposite pheromone updating. As a result, the global search of the proposed ACO algorithm can be significantly enhanced to derive an optimal path compared to the conventional ACO algorithm. The simulation results of the proposed approach perform better in terms of the short distance, mean distance, and success rate towards optimal paths. To further reduce the computation time, the proposed ACO algorithm for path planning is realized on a FPGA chip to verify its practicalities. Experimental results indicate that the efficiency of the path planning is considerably improved by the hardware design for embedded applications.

Original languageEnglish
Pages (from-to)170-179
Number of pages10
JournalJournal of Marine Science and Technology (Taiwan)
Volume26
Issue number2
DOIs
Publication statusPublished - 2018 Jan 1

Fingerprint

Ant colony optimization
pheromone
Motion planning
ant
Field programmable gate arrays (FPGA)
hardware
Tuning
Hardware
planning
simulation

Keywords

  • Ant colony optimization (ACO)
  • Field-programmable gate array (FPGA)
  • Global path planning
  • Pheromone diffusion mechanism

ASJC Scopus subject areas

  • Oceanography
  • Ocean Engineering
  • Mechanics of Materials
  • Mechanical Engineering

Cite this

FPGA implementation of improved ant colony optimization algorithm based on pheromone diffusion mechanism for path planning. / Hsu, Chen-Chien James; Wang, Wei Yen; Chien, Yi Hsing; Hou, Ru Yu.

In: Journal of Marine Science and Technology (Taiwan), Vol. 26, No. 2, 01.01.2018, p. 170-179.

Research output: Contribution to journalArticle

@article{fd78221b8b224d4aa2f157d2a18ad8a5,
title = "FPGA implementation of improved ant colony optimization algorithm based on pheromone diffusion mechanism for path planning",
abstract = "An improved ant colony optimization (ACO) algorithm is proposed in this paper for improving the accuracy of path planning. The main idea of this paper is to avoid local minima by continuously tuning a setting parameter and the establishment of novel mechanisms by means of partial pheromone updating and opposite pheromone updating. As a result, the global search of the proposed ACO algorithm can be significantly enhanced to derive an optimal path compared to the conventional ACO algorithm. The simulation results of the proposed approach perform better in terms of the short distance, mean distance, and success rate towards optimal paths. To further reduce the computation time, the proposed ACO algorithm for path planning is realized on a FPGA chip to verify its practicalities. Experimental results indicate that the efficiency of the path planning is considerably improved by the hardware design for embedded applications.",
keywords = "Ant colony optimization (ACO), Field-programmable gate array (FPGA), Global path planning, Pheromone diffusion mechanism",
author = "Hsu, {Chen-Chien James} and Wang, {Wei Yen} and Chien, {Yi Hsing} and Hou, {Ru Yu}",
year = "2018",
month = "1",
day = "1",
doi = "10.6119/JMST.2018.04_(2).0004",
language = "English",
volume = "26",
pages = "170--179",
journal = "Journal of Marine Science and Technology",
issn = "1023-2796",
publisher = "National Taiwan Ocean University",
number = "2",

}

TY - JOUR

T1 - FPGA implementation of improved ant colony optimization algorithm based on pheromone diffusion mechanism for path planning

AU - Hsu, Chen-Chien James

AU - Wang, Wei Yen

AU - Chien, Yi Hsing

AU - Hou, Ru Yu

PY - 2018/1/1

Y1 - 2018/1/1

N2 - An improved ant colony optimization (ACO) algorithm is proposed in this paper for improving the accuracy of path planning. The main idea of this paper is to avoid local minima by continuously tuning a setting parameter and the establishment of novel mechanisms by means of partial pheromone updating and opposite pheromone updating. As a result, the global search of the proposed ACO algorithm can be significantly enhanced to derive an optimal path compared to the conventional ACO algorithm. The simulation results of the proposed approach perform better in terms of the short distance, mean distance, and success rate towards optimal paths. To further reduce the computation time, the proposed ACO algorithm for path planning is realized on a FPGA chip to verify its practicalities. Experimental results indicate that the efficiency of the path planning is considerably improved by the hardware design for embedded applications.

AB - An improved ant colony optimization (ACO) algorithm is proposed in this paper for improving the accuracy of path planning. The main idea of this paper is to avoid local minima by continuously tuning a setting parameter and the establishment of novel mechanisms by means of partial pheromone updating and opposite pheromone updating. As a result, the global search of the proposed ACO algorithm can be significantly enhanced to derive an optimal path compared to the conventional ACO algorithm. The simulation results of the proposed approach perform better in terms of the short distance, mean distance, and success rate towards optimal paths. To further reduce the computation time, the proposed ACO algorithm for path planning is realized on a FPGA chip to verify its practicalities. Experimental results indicate that the efficiency of the path planning is considerably improved by the hardware design for embedded applications.

KW - Ant colony optimization (ACO)

KW - Field-programmable gate array (FPGA)

KW - Global path planning

KW - Pheromone diffusion mechanism

UR - http://www.scopus.com/inward/record.url?scp=85048938225&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048938225&partnerID=8YFLogxK

U2 - 10.6119/JMST.2018.04_(2).0004

DO - 10.6119/JMST.2018.04_(2).0004

M3 - Article

VL - 26

SP - 170

EP - 179

JO - Journal of Marine Science and Technology

JF - Journal of Marine Science and Technology

SN - 1023-2796

IS - 2

ER -