Trajectory planning on grids

Considering speed limit constraints

Lukáš Chrpa

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

2 Citations (Scopus)

Abstract

Trajectory (path) planning is a well known and thoroughly studied field of automated planning. It is usually used in computer games, robotics or autonomous agent simulations. Grids are often used for regular discretization of continuous space. Many methods exist for trajectory (path) planning on grids, we address the well known A* algorithm and the state-of-the-art Theta* algorithm. Theta* algorithm, as opposed to A*, provides 'any-angle' paths that look more realistic. In this paper, we provide an extension of both these algorithms to enable support for speed limit constraints. We experimentally evaluate and thoroughly discuss how the extensions affect the planning process showing reasonability and justification of our approach.

Original languageEnglish
Title of host publicationEleventh Scandinavian Conference on Artificial Intelligence
PublisherIOS Press
Pages60-69
Number of pages10
Volume227
ISBN (Print)9781607507536
DOIs
Publication statusPublished - 2011
Externally publishedYes

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume227
ISSN (Print)09226389

Fingerprint

Trajectories
Planning
Motion planning
Autonomous agents
Computer games
Robotics

Cite this

Chrpa, L. (2011). Trajectory planning on grids: Considering speed limit constraints. In Eleventh Scandinavian Conference on Artificial Intelligence (Vol. 227, pp. 60-69). (Frontiers in Artificial Intelligence and Applications; Vol. 227). IOS Press. https://doi.org/10.3233/978-1-60750-754-3-60
Chrpa, Lukáš. / Trajectory planning on grids : Considering speed limit constraints. Eleventh Scandinavian Conference on Artificial Intelligence. Vol. 227 IOS Press, 2011. pp. 60-69 (Frontiers in Artificial Intelligence and Applications).
@inproceedings{011a40f7d8e34cadb780c809d61ab326,
title = "Trajectory planning on grids: Considering speed limit constraints",
abstract = "Trajectory (path) planning is a well known and thoroughly studied field of automated planning. It is usually used in computer games, robotics or autonomous agent simulations. Grids are often used for regular discretization of continuous space. Many methods exist for trajectory (path) planning on grids, we address the well known A* algorithm and the state-of-the-art Theta* algorithm. Theta* algorithm, as opposed to A*, provides 'any-angle' paths that look more realistic. In this paper, we provide an extension of both these algorithms to enable support for speed limit constraints. We experimentally evaluate and thoroughly discuss how the extensions affect the planning process showing reasonability and justification of our approach.",
keywords = "Speed limit constraints, Theta*, Trajectory planning A*",
author = "Luk{\'a}š Chrpa",
year = "2011",
doi = "10.3233/978-1-60750-754-3-60",
language = "English",
isbn = "9781607507536",
volume = "227",
series = "Frontiers in Artificial Intelligence and Applications",
publisher = "IOS Press",
pages = "60--69",
booktitle = "Eleventh Scandinavian Conference on Artificial Intelligence",
address = "Netherlands",

}

Chrpa, L 2011, Trajectory planning on grids: Considering speed limit constraints. in Eleventh Scandinavian Conference on Artificial Intelligence. vol. 227, Frontiers in Artificial Intelligence and Applications, vol. 227, IOS Press, pp. 60-69. https://doi.org/10.3233/978-1-60750-754-3-60

Trajectory planning on grids : Considering speed limit constraints. / Chrpa, Lukáš.

Eleventh Scandinavian Conference on Artificial Intelligence. Vol. 227 IOS Press, 2011. p. 60-69 (Frontiers in Artificial Intelligence and Applications; Vol. 227).

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

TY - GEN

T1 - Trajectory planning on grids

T2 - Considering speed limit constraints

AU - Chrpa, Lukáš

PY - 2011

Y1 - 2011

N2 - Trajectory (path) planning is a well known and thoroughly studied field of automated planning. It is usually used in computer games, robotics or autonomous agent simulations. Grids are often used for regular discretization of continuous space. Many methods exist for trajectory (path) planning on grids, we address the well known A* algorithm and the state-of-the-art Theta* algorithm. Theta* algorithm, as opposed to A*, provides 'any-angle' paths that look more realistic. In this paper, we provide an extension of both these algorithms to enable support for speed limit constraints. We experimentally evaluate and thoroughly discuss how the extensions affect the planning process showing reasonability and justification of our approach.

AB - Trajectory (path) planning is a well known and thoroughly studied field of automated planning. It is usually used in computer games, robotics or autonomous agent simulations. Grids are often used for regular discretization of continuous space. Many methods exist for trajectory (path) planning on grids, we address the well known A* algorithm and the state-of-the-art Theta* algorithm. Theta* algorithm, as opposed to A*, provides 'any-angle' paths that look more realistic. In this paper, we provide an extension of both these algorithms to enable support for speed limit constraints. We experimentally evaluate and thoroughly discuss how the extensions affect the planning process showing reasonability and justification of our approach.

KW - Speed limit constraints

KW - Theta

KW - Trajectory planning A

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

U2 - 10.3233/978-1-60750-754-3-60

DO - 10.3233/978-1-60750-754-3-60

M3 - Conference contribution

SN - 9781607507536

VL - 227

T3 - Frontiers in Artificial Intelligence and Applications

SP - 60

EP - 69

BT - Eleventh Scandinavian Conference on Artificial Intelligence

PB - IOS Press

ER -

Chrpa L. Trajectory planning on grids: Considering speed limit constraints. In Eleventh Scandinavian Conference on Artificial Intelligence. Vol. 227. IOS Press. 2011. p. 60-69. (Frontiers in Artificial Intelligence and Applications). https://doi.org/10.3233/978-1-60750-754-3-60