On the Adequacy of Tabu Search for Global Robot Path Planning Problem in Grid Environments

被引：24

作者：

Chaari, Imen ^{[1
,2
]}

Koubaa, Anis ^{[2
,3
,4
]}

Bennaceur, Hachemi ^{[5
]}

Ammar, Adel ^{[5
]}

Trigui, Sahar ^{[1
,2
]}

Tounsi, Mohamed ^{[3
]}

Shakshuki, Elhadi ^{[6
]}

Youssef, Habib ^{[7
]}

机构：

[1] Univ Manouba ENSI, Manouba, Tunisia

[2] Cooperat Intelligent Networked Syst COINS Res Grp, Riadh, Saudi Arabia

[3] Prince Sultan Univ, Coll Comp & Informat Sci, Riadh, Saudi Arabia

[4] Polytech Inst Porto, CISTER INESC TEC, ISEP, Oporto, Portugal

[5] Al Imam Mohamed bin Saud Univ, Res Unit Sci & Technol, Riadh, Saudi Arabia

[6] Acadia Univ, Jodrey Sch Comp Sci, Wolfville, NS B0P 1X0, Canada

[7] Univ Sousse, PRINCE Res Unit, Sousse, Tunisia

来源：

5TH INTERNATIONAL CONFERENCE ON AMBIENT SYSTEMS, NETWORKS AND TECHNOLOGIES (ANT-2014), THE 4TH INTERNATIONAL CONFERENCE ON SUSTAINABLE ENERGY INFORMATION TECHNOLOGY (SEIT-2014) | 2014年 / 32卷

关键词：

Mobile robots; Global path planning; Tabu search;

D O I：

10.1016/j.procs.2014.05.466

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper investigates the capabilities of tabu search for solving the global path planning problem in grid maps. Accordingly, a tabu search system model is designed and a tabu search planner algorithm for solving the path planning problem is proposed. A comprehensive simulation study is conducted using the proposed model and algorithm, in terms of solution quality and execution time. A comparison between our results with those of A* and genetic algorithms (GA) is presented for small, medium and large-scale grid maps. Simulation results show that the tabu search planner is able to find the optimal solution for small scale environments. However, for large scale maps, it provides near-optimal solutions with small gap while ensuring shorter execution times as compared to the A* Algorithm. A discussion about the advantages and limitations of TS for solving a path planning problem is also presented. (C) 2014 Published by Elsevier B.V.

引用

页码：604 / 613

页数：10

共 12 条

[1]

Alajlan M, 2013, 2013 INTERNATIONAL CONFERENCE ON INDIVIDUAL AND COLLECTIVE BEHAVIORS IN ROBOTICS (ICBR), P1, DOI 10.1109/ICBR.2013.6729271

[2] A Tabu search and ant colony system approach for the capacitated location-routing problem [J].

Bouhafs, Lyamine ;

Hajjam, Amir ;

Koukam, Abderrafiaa .

PROCEEDINGS OF NINTH ACIS INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, ARTIFICIAL INTELLIGENCE, NETWORKING AND PARALLEL/DISTRIBUTED COMPUTING, 2008, :46-50

[3] smartPATH: A Hybrid ACO-GA Algorithm for Robot Path Planning [J].

Chaari, Imen ;

Koubaa, Anis ;

Bennaceur, Hachemi ;

Trigui, Sahar ;

Al-Shalfan, Khaled .

2012 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2012,

[4]

Glover F., 1989, ORSA Journal on Computing, V1, P190, DOI [10.1287/ijoc.2.1.4, 10.1287/ijoc.1.3.190]

[5]

Glover F., 1999, Tabu search

[6]

Hussein A., 2012, INT C ENG TECHN ICET, DOI [DOI 10.5772/50568, 10.1109/ICEngTechnol.2012.6396150, DOI 10.1109/ICENGTECHNOL.2012.6396150]

[7]

Masehian E, 2006, IEEE INT C IND TECHN, P2756

[8] Sensor-based robot motion planning - A tabu search approach [J].

Masehian, Ellips ;

Amin-Naseri, Mohammad Reza .

IEEE ROBOTICS & AUTOMATION MAGAZINE, 2008, 15 (02) :48-57

[9]

Quigley M, 2009, IEEE INT CONF ROBOT, P3604

[10]

Raja P, 2012, Int J Phys Sci, P1314, DOI [10.5897/IJPS11.1745, DOI 10.5897/IJPS11.1745]

← 1 2 →