FPGA implementation of improved ant colony optimization algorithm for path planning

Chen Chien Hsu, Wei Yen Wang, Yi Hsing Chien, Ru Yu Hou, Chin Wang Tao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)

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 for updating partial pheromone and opposite pheromone. As a result, the global search of the proposed ACO algorithm can be significantly enhanced in terms of calculating optimal path compared to the conventional ACO algorithm. Simulation results of the proposed approach show better performances in terms of the shortest 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 significantly improved by the hardware design of embedded applications.

Original languageEnglish
Title of host publication2016 IEEE Congress on Evolutionary Computation, CEC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4516-4521
Number of pages6
ISBN (Electronic)9781509006229
DOIs
Publication statusPublished - 2016 Nov 14
Event2016 IEEE Congress on Evolutionary Computation, CEC 2016 - Vancouver, Canada
Duration: 2016 Jul 242016 Jul 29

Publication series

Name2016 IEEE Congress on Evolutionary Computation, CEC 2016

Other

Other2016 IEEE Congress on Evolutionary Computation, CEC 2016
CountryCanada
CityVancouver
Period16/7/2416/7/29

Fingerprint

FPGA Implementation
Ant colony optimization
Path Planning
Motion planning
Field programmable gate arrays (FPGA)
Optimization Algorithm
Pheromone
Optimal Path
Hardware Design
Global Search
Local Minima
Field Programmable Gate Array
Updating
Tuning
Chip
Verify
Hardware
Partial
Experimental Results
Simulation

Keywords

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

ASJC Scopus subject areas

  • Artificial Intelligence
  • Modelling and Simulation
  • Computer Science Applications
  • Control and Optimization

Cite this

Hsu, C. C., Wang, W. Y., Chien, Y. H., Hou, R. Y., & Tao, C. W. (2016). FPGA implementation of improved ant colony optimization algorithm for path planning. In 2016 IEEE Congress on Evolutionary Computation, CEC 2016 (pp. 4516-4521). [7744364] (2016 IEEE Congress on Evolutionary Computation, CEC 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CEC.2016.7744364

FPGA implementation of improved ant colony optimization algorithm for path planning. / Hsu, Chen Chien; Wang, Wei Yen; Chien, Yi Hsing; Hou, Ru Yu; Tao, Chin Wang.

2016 IEEE Congress on Evolutionary Computation, CEC 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 4516-4521 7744364 (2016 IEEE Congress on Evolutionary Computation, CEC 2016).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Hsu, CC, Wang, WY, Chien, YH, Hou, RY & Tao, CW 2016, FPGA implementation of improved ant colony optimization algorithm for path planning. in 2016 IEEE Congress on Evolutionary Computation, CEC 2016., 7744364, 2016 IEEE Congress on Evolutionary Computation, CEC 2016, Institute of Electrical and Electronics Engineers Inc., pp. 4516-4521, 2016 IEEE Congress on Evolutionary Computation, CEC 2016, Vancouver, Canada, 16/7/24. https://doi.org/10.1109/CEC.2016.7744364
Hsu CC, Wang WY, Chien YH, Hou RY, Tao CW. FPGA implementation of improved ant colony optimization algorithm for path planning. In 2016 IEEE Congress on Evolutionary Computation, CEC 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 4516-4521. 7744364. (2016 IEEE Congress on Evolutionary Computation, CEC 2016). https://doi.org/10.1109/CEC.2016.7744364
Hsu, Chen Chien ; Wang, Wei Yen ; Chien, Yi Hsing ; Hou, Ru Yu ; Tao, Chin Wang. / FPGA implementation of improved ant colony optimization algorithm for path planning. 2016 IEEE Congress on Evolutionary Computation, CEC 2016. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 4516-4521 (2016 IEEE Congress on Evolutionary Computation, CEC 2016).
@inproceedings{5c9226b54d174702bfe9fb3e37be8e49,
title = "FPGA implementation of improved ant colony optimization algorithm 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 for updating partial pheromone and opposite pheromone. As a result, the global search of the proposed ACO algorithm can be significantly enhanced in terms of calculating optimal path compared to the conventional ACO algorithm. Simulation results of the proposed approach show better performances in terms of the shortest 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 significantly improved by the hardware design of embedded applications.",
keywords = "Ant colony optimization (ACO), Field-programmable gate array (FPGA), Path planning, Pheromone diffusion mechanism",
author = "Hsu, {Chen Chien} and Wang, {Wei Yen} and Chien, {Yi Hsing} and Hou, {Ru Yu} and Tao, {Chin Wang}",
year = "2016",
month = "11",
day = "14",
doi = "10.1109/CEC.2016.7744364",
language = "English",
series = "2016 IEEE Congress on Evolutionary Computation, CEC 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "4516--4521",
booktitle = "2016 IEEE Congress on Evolutionary Computation, CEC 2016",

}

TY - GEN

T1 - FPGA implementation of improved ant colony optimization algorithm for path planning

AU - Hsu, Chen Chien

AU - Wang, Wei Yen

AU - Chien, Yi Hsing

AU - Hou, Ru Yu

AU - Tao, Chin Wang

PY - 2016/11/14

Y1 - 2016/11/14

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 for updating partial pheromone and opposite pheromone. As a result, the global search of the proposed ACO algorithm can be significantly enhanced in terms of calculating optimal path compared to the conventional ACO algorithm. Simulation results of the proposed approach show better performances in terms of the shortest 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 significantly improved by the hardware design of 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 for updating partial pheromone and opposite pheromone. As a result, the global search of the proposed ACO algorithm can be significantly enhanced in terms of calculating optimal path compared to the conventional ACO algorithm. Simulation results of the proposed approach show better performances in terms of the shortest 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 significantly improved by the hardware design of embedded applications.

KW - Ant colony optimization (ACO)

KW - Field-programmable gate array (FPGA)

KW - Path planning

KW - Pheromone diffusion mechanism

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

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

U2 - 10.1109/CEC.2016.7744364

DO - 10.1109/CEC.2016.7744364

M3 - Conference contribution

AN - SCOPUS:85008259361

T3 - 2016 IEEE Congress on Evolutionary Computation, CEC 2016

SP - 4516

EP - 4521

BT - 2016 IEEE Congress on Evolutionary Computation, CEC 2016

PB - Institute of Electrical and Electronics Engineers Inc.

ER -