Publication detail

Path Optimization by Graph Algorithms

ŠKORPIL, V. ŠŤASTNÝ, J. ČÍŽEK, L.

Original Title

Path Optimization by Graph Algorithms

English Title

Path Optimization by Graph Algorithms

Type

conference paper

Language

en

Original Abstract

Many different methods of optimizing the path exist in an environment with obstacles. Two methods for path planning by means of graph-based algorithms are compared in this article. These algorithms are Anytime Repairing A *, which is designed for quickly finding the path under time pressure and its potential improvement in the remaining time and the classical A*, which the previous algorithm is based on. These algorithms are tested on four different scenes with different levels of difficulty and the results are compared according to the time of optimization, number of newly searched states and the length of the path found. In our research we tested also the D* Lite algorithm. This algorithm will be described in some next paper.

English abstract

Many different methods of optimizing the path exist in an environment with obstacles. Two methods for path planning by means of graph-based algorithms are compared in this article. These algorithms are Anytime Repairing A *, which is designed for quickly finding the path under time pressure and its potential improvement in the remaining time and the classical A*, which the previous algorithm is based on. These algorithms are tested on four different scenes with different levels of difficulty and the results are compared according to the time of optimization, number of newly searched states and the length of the path found. In our research we tested also the D* Lite algorithm. This algorithm will be described in some next paper.

Keywords

Path Planning, Graph-based Algorithms, Algorithm A *, Algorithm ARA *, Path Optimizing, Pseudocode, Procedure

RIV year

2012

Released

14.07.2012

Publisher

WSEAS

Location

Greece, Iskand Kos

ISBN

978-1-61804-109-8

Book

Recent Researches in Communications and Computers

Edition

WSEAS

Edition number

1

Pages from

73

Pages to

77

Pages count

5

BibTex


@inproceedings{BUT94171,
  author="Vladislav {Škorpil} and Jiří {Šťastný} and Lubomír {Čížek}",
  title="Path Optimization by Graph Algorithms",
  annote="Many different methods of optimizing the path exist in an environment with obstacles. Two methods for path planning by means of graph-based algorithms are compared in this article. These algorithms are Anytime Repairing A *, which is designed for quickly finding the path under time pressure and its potential improvement in the remaining time and the classical A*, which the previous algorithm is based on. These algorithms are tested on four different scenes with different levels of difficulty and the results are compared according to the time of optimization, number of newly searched states and the length of the path found. In our research we tested also the D* Lite algorithm. This algorithm will be described in some next paper.",
  address="WSEAS",
  booktitle="Recent Researches in Communications and Computers",
  chapter="94171",
  edition="WSEAS",
  howpublished="print",
  institution="WSEAS",
  year="2012",
  month="july",
  pages="73--77",
  publisher="WSEAS",
  type="conference paper"
}