Skip to main content

High-Speed Planning and Reducing Memory Usage of a Precomputed Search Tree Using Pruning

Buy Article:

$63.00 plus tax (Refund Policy)

Abstract:

We present a high-speed planning method with compact precomputed search trees using a new pruning method, and evaluate the effectiveness and the efficiency of our precomputation planning. Its speed is faster than an A* planner in maps in which the obstacle rate is the same as indoor environments. Precomputed search trees are one way of reducing planning time; however, there is a time–memory trade-off. Our precomputed search tree (PCS) is built with pruning based on a rate of constant memory — the maximum size pruning (MSP) method, which is a preset ratio of pruning. Using MSP, we get a large precomputed search tree that is a reasonable size. Additionally we apply the node selection strategy to MSP. We extend the outer edge of the tree and enhance the path reachability. The alternate branch backtracking enhances the success rate in crowded environments. In maps with less than 20% obstacle rates on them, the run-time of precomputation planning is more than an order of magnitude faster than the planning without precomputed search trees. Our precomputed tree finds a optimal path in maps with 25% obstacle rates. Thus, our precomputation planning speedily produces the optimal path in indoor environments.

Keywords: ALTERNATE BRANCH BACK-TRACKING; MAXIMUM SIZE PRUNING METHOD; NODE SELECTION STRATEGY; PRECOMPUTED SEARCH TREE

Document Type: Research Article

DOI: https://doi.org/10.1163/016918610X493660

Affiliations: 1: Graduate School of Information Science, Nara Institute of Science and Technology 8916-5 Takayama-cho, Ikoma-shi, Nara 630-0192, Japan, Digital Human Research Center, National Institute of Advanced Industrial Science and Technology 2-3-26, Aomi, Kouto-ku, Tokyo 135-0064, Japan;, Email: suzuki-yumiko@aist.go.jp 2: Digital Human Research Center, National Institute of Advanced Industrial Science and Technology 2-3-26, Aomi, Kouto-ku, Tokyo 135-0064, Japan 3: Graduate School of Information Science, Nara Institute of Science and Technology 8916-5 Takayama-cho, Ikoma-shi, Nara 630-0192, Japan, Digital Human Research Center, National Institute of Advanced Industrial Science and Technology 2-3-26, Aomi, Kouto-ku, Tokyo 135-0064, Japan

Publication date: 2010-04-01

  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content
Cookie Policy
X
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more