Runtime reduction in optimal multi-query sampling-based motion planning

Weria Khaksar, Khairul Salleh Bin Mohamed Sahari, Firas B. Ismail, Moslem Yousefi, Marwan A. Ali

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

Abstract

Sampling-based motion planning algorithms have been successfully applied to various types of high-dimensional planning tasks. Recently an extension of PRM algorithm called PRM∗ planner has been proposed which guarantees asymptotic optimal solutions in terms of path length. However, the high runtime of sampling-based algorithms is still a serious disadvantage. In this paper, a new extension of PRM planner is proposed which incorporates the variable neighborhood radius feature of PRM∗ and the sampling radius of low-dispersion sampling in order to improve the cost of the generated solutions in terms of path length and runtime. The performance of the proposed algorithm is tested in different planning environments. Furthermore, the proposed planner is compared to the original PRM and the PRM∗ approaches and shows significant improvement.

Original languageEnglish
Title of host publication2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages52-56
Number of pages5
ISBN (Electronic)9781479957651
DOIs
Publication statusPublished - 09 Oct 2015
EventIEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014 - Kuala Lumpur, Malaysia
Duration: 15 Dec 201416 Dec 2014

Publication series

Name2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014

Other

OtherIEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014
CountryMalaysia
CityKuala Lumpur
Period15/12/1416/12/14

Fingerprint

Motion planning
Sampling
Planning
Costs

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Industrial and Manufacturing Engineering
  • Mechanical Engineering

Cite this

Khaksar, W., Sahari, K. S. B. M., Ismail, F. B., Yousefi, M., & Ali, M. A. (2015). Runtime reduction in optimal multi-query sampling-based motion planning. In 2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014 (pp. 52-56). [7295861] (2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ROMA.2014.7295861
Khaksar, Weria ; Sahari, Khairul Salleh Bin Mohamed ; Ismail, Firas B. ; Yousefi, Moslem ; Ali, Marwan A. / Runtime reduction in optimal multi-query sampling-based motion planning. 2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 52-56 (2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014).
@inproceedings{f5a1a0cc2d464e4c8cb4e2487b2d58da,
title = "Runtime reduction in optimal multi-query sampling-based motion planning",
abstract = "Sampling-based motion planning algorithms have been successfully applied to various types of high-dimensional planning tasks. Recently an extension of PRM algorithm called PRM∗ planner has been proposed which guarantees asymptotic optimal solutions in terms of path length. However, the high runtime of sampling-based algorithms is still a serious disadvantage. In this paper, a new extension of PRM planner is proposed which incorporates the variable neighborhood radius feature of PRM∗ and the sampling radius of low-dispersion sampling in order to improve the cost of the generated solutions in terms of path length and runtime. The performance of the proposed algorithm is tested in different planning environments. Furthermore, the proposed planner is compared to the original PRM and the PRM∗ approaches and shows significant improvement.",
author = "Weria Khaksar and Sahari, {Khairul Salleh Bin Mohamed} and Ismail, {Firas B.} and Moslem Yousefi and Ali, {Marwan A.}",
year = "2015",
month = "10",
day = "9",
doi = "10.1109/ROMA.2014.7295861",
language = "English",
series = "2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "52--56",
booktitle = "2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014",
address = "United States",

}

Khaksar, W, Sahari, KSBM, Ismail, FB, Yousefi, M & Ali, MA 2015, Runtime reduction in optimal multi-query sampling-based motion planning. in 2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014., 7295861, 2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014, Institute of Electrical and Electronics Engineers Inc., pp. 52-56, IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014, Kuala Lumpur, Malaysia, 15/12/14. https://doi.org/10.1109/ROMA.2014.7295861

Runtime reduction in optimal multi-query sampling-based motion planning. / Khaksar, Weria; Sahari, Khairul Salleh Bin Mohamed; Ismail, Firas B.; Yousefi, Moslem; Ali, Marwan A.

2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014. Institute of Electrical and Electronics Engineers Inc., 2015. p. 52-56 7295861 (2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014).

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

TY - GEN

T1 - Runtime reduction in optimal multi-query sampling-based motion planning

AU - Khaksar, Weria

AU - Sahari, Khairul Salleh Bin Mohamed

AU - Ismail, Firas B.

AU - Yousefi, Moslem

AU - Ali, Marwan A.

PY - 2015/10/9

Y1 - 2015/10/9

N2 - Sampling-based motion planning algorithms have been successfully applied to various types of high-dimensional planning tasks. Recently an extension of PRM algorithm called PRM∗ planner has been proposed which guarantees asymptotic optimal solutions in terms of path length. However, the high runtime of sampling-based algorithms is still a serious disadvantage. In this paper, a new extension of PRM planner is proposed which incorporates the variable neighborhood radius feature of PRM∗ and the sampling radius of low-dispersion sampling in order to improve the cost of the generated solutions in terms of path length and runtime. The performance of the proposed algorithm is tested in different planning environments. Furthermore, the proposed planner is compared to the original PRM and the PRM∗ approaches and shows significant improvement.

AB - Sampling-based motion planning algorithms have been successfully applied to various types of high-dimensional planning tasks. Recently an extension of PRM algorithm called PRM∗ planner has been proposed which guarantees asymptotic optimal solutions in terms of path length. However, the high runtime of sampling-based algorithms is still a serious disadvantage. In this paper, a new extension of PRM planner is proposed which incorporates the variable neighborhood radius feature of PRM∗ and the sampling radius of low-dispersion sampling in order to improve the cost of the generated solutions in terms of path length and runtime. The performance of the proposed algorithm is tested in different planning environments. Furthermore, the proposed planner is compared to the original PRM and the PRM∗ approaches and shows significant improvement.

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

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

U2 - 10.1109/ROMA.2014.7295861

DO - 10.1109/ROMA.2014.7295861

M3 - Conference contribution

AN - SCOPUS:84959465777

T3 - 2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014

SP - 52

EP - 56

BT - 2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Khaksar W, Sahari KSBM, Ismail FB, Yousefi M, Ali MA. Runtime reduction in optimal multi-query sampling-based motion planning. In 2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014. Institute of Electrical and Electronics Engineers Inc. 2015. p. 52-56. 7295861. (2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014). https://doi.org/10.1109/ROMA.2014.7295861