Optimum path planning using convex hull and local search heuristic algorithms

S. Meeran, A. Shafie

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

Whether in improving quality or productivity the impact of mechatronic systems such as robots in industry is unquestionable. One aspect of interest in robotics is planning the optimum path for a mobile robot or the optimum trajectory for link movements of a stationary robot in order to increase their efficiency. However, for a given set of points complete enumeration of all the possible paths to establish an optimal one is not feasible as the search space increases exponentially (explodes combinatorially) as the number of points increases. This problem, traditionally known as the "Traveling Salesman Problem" (TSP) has attracted a great deal of attention for a long time. Proven enumerative techniques such as "nearest neighbour algorithm", "branch and bound", "cutting planes", and "dynamic programming" as well as approximation methods such as "tabu search", "greedy algorithm", "simulated annealing" and "genetic algorithm", have had only a limited success in solving this problem. Recently "convex hull", a minimum area and perimeter shape, has been used as an initial sub-tour along with enumerative techniques such as minimising insertion costs to solve the TSP problem. We present a system which uses heuristic rules to augment the convex hull initial sub-tour created by the Graham scan algorithm. The system is able to provide a solution in a polynomial time.

Original languageEnglish
Pages (from-to)737-756
Number of pages20
JournalMechatronics
Volume7
Issue number8
DOIs
Publication statusPublished - 1 Dec 1997

Fingerprint

Heuristic algorithms
Motion planning
Traveling salesman problem
Robots
Tabu search
Mechatronics
Simulated annealing
Dynamic programming
Mobile robots
Robotics
Genetic algorithms
Productivity
Trajectories
Polynomials
Planning
Local search (optimization)
Costs
Industry

ASJC Scopus subject areas

  • Mechanical Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this

Optimum path planning using convex hull and local search heuristic algorithms. / Meeran, S.; Shafie, A.

In: Mechatronics, Vol. 7, No. 8, 01.12.1997, p. 737-756.

Research output: Contribution to journalArticle

@article{a05e2145ab114ecaa09d8e33aa4b0032,
title = "Optimum path planning using convex hull and local search heuristic algorithms",
abstract = "Whether in improving quality or productivity the impact of mechatronic systems such as robots in industry is unquestionable. One aspect of interest in robotics is planning the optimum path for a mobile robot or the optimum trajectory for link movements of a stationary robot in order to increase their efficiency. However, for a given set of points complete enumeration of all the possible paths to establish an optimal one is not feasible as the search space increases exponentially (explodes combinatorially) as the number of points increases. This problem, traditionally known as the {"}Traveling Salesman Problem{"} (TSP) has attracted a great deal of attention for a long time. Proven enumerative techniques such as {"}nearest neighbour algorithm{"}, {"}branch and bound{"}, {"}cutting planes{"}, and {"}dynamic programming{"} as well as approximation methods such as {"}tabu search{"}, {"}greedy algorithm{"}, {"}simulated annealing{"} and {"}genetic algorithm{"}, have had only a limited success in solving this problem. Recently {"}convex hull{"}, a minimum area and perimeter shape, has been used as an initial sub-tour along with enumerative techniques such as minimising insertion costs to solve the TSP problem. We present a system which uses heuristic rules to augment the convex hull initial sub-tour created by the Graham scan algorithm. The system is able to provide a solution in a polynomial time.",
author = "S. Meeran and A. Shafie",
year = "1997",
month = "12",
day = "1",
doi = "10.1016/S0957-4158(97)00033-0",
language = "English",
volume = "7",
pages = "737--756",
journal = "Mechatronics",
issn = "0957-4158",
publisher = "Elsevier",
number = "8",

}

TY - JOUR

T1 - Optimum path planning using convex hull and local search heuristic algorithms

AU - Meeran, S.

AU - Shafie, A.

PY - 1997/12/1

Y1 - 1997/12/1

N2 - Whether in improving quality or productivity the impact of mechatronic systems such as robots in industry is unquestionable. One aspect of interest in robotics is planning the optimum path for a mobile robot or the optimum trajectory for link movements of a stationary robot in order to increase their efficiency. However, for a given set of points complete enumeration of all the possible paths to establish an optimal one is not feasible as the search space increases exponentially (explodes combinatorially) as the number of points increases. This problem, traditionally known as the "Traveling Salesman Problem" (TSP) has attracted a great deal of attention for a long time. Proven enumerative techniques such as "nearest neighbour algorithm", "branch and bound", "cutting planes", and "dynamic programming" as well as approximation methods such as "tabu search", "greedy algorithm", "simulated annealing" and "genetic algorithm", have had only a limited success in solving this problem. Recently "convex hull", a minimum area and perimeter shape, has been used as an initial sub-tour along with enumerative techniques such as minimising insertion costs to solve the TSP problem. We present a system which uses heuristic rules to augment the convex hull initial sub-tour created by the Graham scan algorithm. The system is able to provide a solution in a polynomial time.

AB - Whether in improving quality or productivity the impact of mechatronic systems such as robots in industry is unquestionable. One aspect of interest in robotics is planning the optimum path for a mobile robot or the optimum trajectory for link movements of a stationary robot in order to increase their efficiency. However, for a given set of points complete enumeration of all the possible paths to establish an optimal one is not feasible as the search space increases exponentially (explodes combinatorially) as the number of points increases. This problem, traditionally known as the "Traveling Salesman Problem" (TSP) has attracted a great deal of attention for a long time. Proven enumerative techniques such as "nearest neighbour algorithm", "branch and bound", "cutting planes", and "dynamic programming" as well as approximation methods such as "tabu search", "greedy algorithm", "simulated annealing" and "genetic algorithm", have had only a limited success in solving this problem. Recently "convex hull", a minimum area and perimeter shape, has been used as an initial sub-tour along with enumerative techniques such as minimising insertion costs to solve the TSP problem. We present a system which uses heuristic rules to augment the convex hull initial sub-tour created by the Graham scan algorithm. The system is able to provide a solution in a polynomial time.

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

U2 - 10.1016/S0957-4158(97)00033-0

DO - 10.1016/S0957-4158(97)00033-0

M3 - Article

VL - 7

SP - 737

EP - 756

JO - Mechatronics

JF - Mechatronics

SN - 0957-4158

IS - 8

ER -