A novel scalable parallel algorithm for finding optimal paths over heterogeneous terrain

Carsten Maple; Jon Hitchcock

doi:10.1109/IV.2005.12

A novel scalable parallel algorithm for finding optimal paths over heterogeneous terrain

Carsten Maple
, Jon Hitchcock

Institute for Research in Applicable Computing (IRAC)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

The area of path planning has received a great deal of attention recently. Algorithms are required that can deliver optimal paths for robots to take over homogeneous or non-homogeneous terrain. Optimal paths may be those that involve the shortest distance travelled, the least number of turns or the least number of ascents and descents. The often highly complex nature of terrains and the necessity for realtime solutions have lead to a requirement for the development of parallel algorithms. Such problems have been notoriously difficult to parallelise efficiently; indeed it has been said that an efficiency of 25-60% should be considered a success. In this paper we present a parallel algorithm for finding optimal paths over non-homogeneous terrain that demonstrates superlinear speed-up.

Original language	English
Title of host publication	nan
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Print)	0769523978
DOIs	https://doi.org/10.1109/IV.2005.12
Publication status	Published - 15 Sept 2005
Event	Ninth International Conference on Information Visualisation (IV'05) - London Duration: 6 Jul 2005 → 8 Jul 2005

Conference

Conference	Ninth International Conference on Information Visualisation (IV'05)
City	London
Period	6/07/05 → 8/07/05
Other	Ninth International Conference on Information Visualisation (IV'05) (06/07/2005-08/07/2005, London)

Keywords

parallel computing

Access to Document

10.1109/IV.2005.12

https://ieeexplore.ieee.org/document/1509145

Handle.net

Persistent link

Cite this

@inproceedings{c4610d16fb8f49a39b5f1f180018b99e,

title = "A novel scalable parallel algorithm for finding optimal paths over heterogeneous terrain",

abstract = "The area of path planning has received a great deal of attention recently. Algorithms are required that can deliver optimal paths for robots to take over homogeneous or non-homogeneous terrain. Optimal paths may be those that involve the shortest distance travelled, the least number of turns or the least number of ascents and descents. The often highly complex nature of terrains and the necessity for realtime solutions have lead to a requirement for the development of parallel algorithms. Such problems have been notoriously difficult to parallelise efficiently; indeed it has been said that an efficiency of 25-60\% should be considered a success. In this paper we present a parallel algorithm for finding optimal paths over non-homogeneous terrain that demonstrates superlinear speed-up.",

keywords = "parallel computing",

author = "Carsten Maple and Jon Hitchcock",

year = "2005",

month = sep,

day = "15",

doi = "10.1109/IV.2005.12",

language = "English",

isbn = "0769523978",

booktitle = "nan",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

note = "Ninth International Conference on Information Visualisation (IV'05) ; Conference date: 06-07-2005 Through 08-07-2005",

}

TY - GEN

T1 - A novel scalable parallel algorithm for finding optimal paths over heterogeneous terrain

AU - Maple, Carsten

AU - Hitchcock, Jon

PY - 2005/9/15

Y1 - 2005/9/15

N2 - The area of path planning has received a great deal of attention recently. Algorithms are required that can deliver optimal paths for robots to take over homogeneous or non-homogeneous terrain. Optimal paths may be those that involve the shortest distance travelled, the least number of turns or the least number of ascents and descents. The often highly complex nature of terrains and the necessity for realtime solutions have lead to a requirement for the development of parallel algorithms. Such problems have been notoriously difficult to parallelise efficiently; indeed it has been said that an efficiency of 25-60% should be considered a success. In this paper we present a parallel algorithm for finding optimal paths over non-homogeneous terrain that demonstrates superlinear speed-up.

AB - The area of path planning has received a great deal of attention recently. Algorithms are required that can deliver optimal paths for robots to take over homogeneous or non-homogeneous terrain. Optimal paths may be those that involve the shortest distance travelled, the least number of turns or the least number of ascents and descents. The often highly complex nature of terrains and the necessity for realtime solutions have lead to a requirement for the development of parallel algorithms. Such problems have been notoriously difficult to parallelise efficiently; indeed it has been said that an efficiency of 25-60% should be considered a success. In this paper we present a parallel algorithm for finding optimal paths over non-homogeneous terrain that demonstrates superlinear speed-up.

KW - parallel computing

U2 - 10.1109/IV.2005.12

DO - 10.1109/IV.2005.12

M3 - Conference contribution

SN - 0769523978

BT - nan

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - Ninth International Conference on Information Visualisation (IV'05)

Y2 - 6 July 2005 through 8 July 2005

ER -

A novel scalable parallel algorithm for finding optimal paths over heterogeneous terrain

Abstract

Conference

Keywords

Access to Document

Handle.net

Fingerprint

Cite this