Using random sampling trees for automated planning

Article type: Research Article

Authors: Alcázar, Vidal^{a; *} | Fernández, Susana^a | Borrajo, Daniel^a | Veloso, Manuela^b

Affiliations: [a] Computer Science Department, Universidad Carlos III de Madrid, Madrid, Spain. E-mails: vidal.alcazar.saiz@gmail.com, sfarregu@inf.uc3m.es, dborrajo@ia.uc3m.es | [b] Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA. E-mail: mmv@cs.cmu.edu

Correspondence: [*] Corresponding author. E-mail: vidal.alcazar.saiz@gmail.com.

Abstract: Rapidly-exploring Random Trees (RRTs) are data structures and search algorithms designed to be used in continuous path planning problems. They are one of the most successful state-of-the-art techniques in motion planning, as they offer a great degree of flexibility and reliability. However, their use in other fields in which search is a commonly used approach has not been thoroughly analyzed. In this work we propose the use of RRTs as a search algorithm for automated planning. We analyze the advantages and disadvantages that this approach has over previously used search algorithms and the challenges of adapting RRTs for implicit and discrete search spaces.

Keywords: Automated planning, heuristic search, random sampling

DOI: 10.3233/AIC-150658

Journal: AI Communications, vol. 28, no. 4, pp. 665-681, 2015