An optimal approach to anytime task and path planning for autonomous mobile robots in dynamic environments

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

Abstract

The study of combined task and path planning has mainly focused on feasibility planning for high-dimensional, complex manipulation problems. Yet the integration of symbolic reasoning capabilities with geometric knowledge can address optimal planning in lower dimensional problems. This paper presents a dynamic, anytime task and path planning approach that enables mobile robots to autonomously adapt to changes in the environment. The planner consists of a path planning layer that adopts a multi-tree extension of the optimal Transition-based Rapidly-Exploring Random Tree algorithm to simultaneously find optimal paths for all movement actions. The corresponding path costs, derived from a cost space function, are incorporated into the symbolic representation of the problem to guide the task planning layer. Anytime planning provides continuous path quality improvements, which subsequently updates the high-level plan. Geometric knowledge of the environment is preserved to efficiently re-plan both at the task and path planning level. The planner is evaluated against existing methods for static planning problems, showing that it is able to find higher quality plans without compromising planning time. Simulated deployment of the planner in a partially-known environment demonstrates the effectiveness of the dynamic, anytime components.
LanguageEnglish
Title of host publicationTowards Autonomous Robotic Systems
Subtitle of host publication20th Annual Conference, TAROS 2019, London, UK, July 3–5, 2019, Proceedings, Part II
EditorsKasper Althoefer, Jelizaveta Konstantinova, Ketao Zhang
Place of PublicationCham
Pages155-166
Number of pages12
DOIs
Publication statusPublished - 8 Aug 2019

Publication series

NameLecture Notes in Computer Science
Volume11650
ISSN (Print)0302-9743

Fingerprint

Motion planning
Mobile robots
Planning
Costs

Keywords

  • robotics
  • autonomous systems
  • task planning
  • path planning
  • combined task and motion planning
  • dynamic planning

Cite this

Wong, C., Yang, E., Yan, X-T., & Gu, D. (2019). An optimal approach to anytime task and path planning for autonomous mobile robots in dynamic environments. In K. Althoefer, J. Konstantinova, & K. Zhang (Eds.), Towards Autonomous Robotic Systems: 20th Annual Conference, TAROS 2019, London, UK, July 3–5, 2019, Proceedings, Part II (pp. 155-166). (Lecture Notes in Computer Science; Vol. 11650). Cham. https://doi.org/10.1007/978-3-030-25332-5_14
Wong, Cuebong ; Yang, Erfu ; Yan, Xiu-Tian ; Gu, Dongbing. / An optimal approach to anytime task and path planning for autonomous mobile robots in dynamic environments. Towards Autonomous Robotic Systems: 20th Annual Conference, TAROS 2019, London, UK, July 3–5, 2019, Proceedings, Part II. editor / Kasper Althoefer ; Jelizaveta Konstantinova ; Ketao Zhang. Cham, 2019. pp. 155-166 (Lecture Notes in Computer Science).
@inproceedings{506c6113d5f84856b3e622e004435fbc,
title = "An optimal approach to anytime task and path planning for autonomous mobile robots in dynamic environments",
abstract = "The study of combined task and path planning has mainly focused on feasibility planning for high-dimensional, complex manipulation problems. Yet the integration of symbolic reasoning capabilities with geometric knowledge can address optimal planning in lower dimensional problems. This paper presents a dynamic, anytime task and path planning approach that enables mobile robots to autonomously adapt to changes in the environment. The planner consists of a path planning layer that adopts a multi-tree extension of the optimal Transition-based Rapidly-Exploring Random Tree algorithm to simultaneously find optimal paths for all movement actions. The corresponding path costs, derived from a cost space function, are incorporated into the symbolic representation of the problem to guide the task planning layer. Anytime planning provides continuous path quality improvements, which subsequently updates the high-level plan. Geometric knowledge of the environment is preserved to efficiently re-plan both at the task and path planning level. The planner is evaluated against existing methods for static planning problems, showing that it is able to find higher quality plans without compromising planning time. Simulated deployment of the planner in a partially-known environment demonstrates the effectiveness of the dynamic, anytime components.",
keywords = "robotics, autonomous systems, task planning, path planning, combined task and motion planning, dynamic planning",
author = "Cuebong Wong and Erfu Yang and Xiu-Tian Yan and Dongbing Gu",
note = "This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science, vol 11650. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-25332-5_14.",
year = "2019",
month = "8",
day = "8",
doi = "10.1007/978-3-030-25332-5_14",
language = "English",
isbn = "9783030253318",
series = "Lecture Notes in Computer Science",
pages = "155--166",
editor = "Kasper Althoefer and Konstantinova, {Jelizaveta } and Ketao Zhang",
booktitle = "Towards Autonomous Robotic Systems",

}

Wong, C, Yang, E, Yan, X-T & Gu, D 2019, An optimal approach to anytime task and path planning for autonomous mobile robots in dynamic environments. in K Althoefer, J Konstantinova & K Zhang (eds), Towards Autonomous Robotic Systems: 20th Annual Conference, TAROS 2019, London, UK, July 3–5, 2019, Proceedings, Part II. Lecture Notes in Computer Science, vol. 11650, Cham, pp. 155-166. https://doi.org/10.1007/978-3-030-25332-5_14

An optimal approach to anytime task and path planning for autonomous mobile robots in dynamic environments. / Wong, Cuebong; Yang, Erfu; Yan, Xiu-Tian; Gu, Dongbing.

Towards Autonomous Robotic Systems: 20th Annual Conference, TAROS 2019, London, UK, July 3–5, 2019, Proceedings, Part II. ed. / Kasper Althoefer; Jelizaveta Konstantinova; Ketao Zhang. Cham, 2019. p. 155-166 (Lecture Notes in Computer Science; Vol. 11650).

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

TY - GEN

T1 - An optimal approach to anytime task and path planning for autonomous mobile robots in dynamic environments

AU - Wong, Cuebong

AU - Yang, Erfu

AU - Yan, Xiu-Tian

AU - Gu, Dongbing

N1 - This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science, vol 11650. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-25332-5_14.

PY - 2019/8/8

Y1 - 2019/8/8

N2 - The study of combined task and path planning has mainly focused on feasibility planning for high-dimensional, complex manipulation problems. Yet the integration of symbolic reasoning capabilities with geometric knowledge can address optimal planning in lower dimensional problems. This paper presents a dynamic, anytime task and path planning approach that enables mobile robots to autonomously adapt to changes in the environment. The planner consists of a path planning layer that adopts a multi-tree extension of the optimal Transition-based Rapidly-Exploring Random Tree algorithm to simultaneously find optimal paths for all movement actions. The corresponding path costs, derived from a cost space function, are incorporated into the symbolic representation of the problem to guide the task planning layer. Anytime planning provides continuous path quality improvements, which subsequently updates the high-level plan. Geometric knowledge of the environment is preserved to efficiently re-plan both at the task and path planning level. The planner is evaluated against existing methods for static planning problems, showing that it is able to find higher quality plans without compromising planning time. Simulated deployment of the planner in a partially-known environment demonstrates the effectiveness of the dynamic, anytime components.

AB - The study of combined task and path planning has mainly focused on feasibility planning for high-dimensional, complex manipulation problems. Yet the integration of symbolic reasoning capabilities with geometric knowledge can address optimal planning in lower dimensional problems. This paper presents a dynamic, anytime task and path planning approach that enables mobile robots to autonomously adapt to changes in the environment. The planner consists of a path planning layer that adopts a multi-tree extension of the optimal Transition-based Rapidly-Exploring Random Tree algorithm to simultaneously find optimal paths for all movement actions. The corresponding path costs, derived from a cost space function, are incorporated into the symbolic representation of the problem to guide the task planning layer. Anytime planning provides continuous path quality improvements, which subsequently updates the high-level plan. Geometric knowledge of the environment is preserved to efficiently re-plan both at the task and path planning level. The planner is evaluated against existing methods for static planning problems, showing that it is able to find higher quality plans without compromising planning time. Simulated deployment of the planner in a partially-known environment demonstrates the effectiveness of the dynamic, anytime components.

KW - robotics

KW - autonomous systems

KW - task planning

KW - path planning

KW - combined task and motion planning

KW - dynamic planning

U2 - 10.1007/978-3-030-25332-5_14

DO - 10.1007/978-3-030-25332-5_14

M3 - Conference contribution book

SN - 9783030253318

T3 - Lecture Notes in Computer Science

SP - 155

EP - 166

BT - Towards Autonomous Robotic Systems

A2 - Althoefer, Kasper

A2 - Konstantinova, Jelizaveta

A2 - Zhang, Ketao

CY - Cham

ER -

Wong C, Yang E, Yan X-T, Gu D. An optimal approach to anytime task and path planning for autonomous mobile robots in dynamic environments. In Althoefer K, Konstantinova J, Zhang K, editors, Towards Autonomous Robotic Systems: 20th Annual Conference, TAROS 2019, London, UK, July 3–5, 2019, Proceedings, Part II. Cham. 2019. p. 155-166. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-030-25332-5_14