Top > JRM > Effectiveness Evaluation of Precomputation Search Using Steeri ...

single-rb.php

JRM Vol.22 No.1 pp. 112-121
doi: 10.20965/jrm.2010.p0112
(2010)

Paper:

Views over last 60 days: 429

Effectiveness Evaluation of Precomputation Search Using Steering Sets

Yumiko Suzuki*,**, Simon Thompson**, and Satoshi Kagami*,**

*Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama-cho, Ikoma, Nara 630-0192, Japan

**Digital Human Research Center, National Institute of Advanced Science and Technology, 2-3-26 Aomi, Koto-ku, Tokyo 135-0064, Japan

Received:
March 26, 2009
Accepted:
December 25, 2009
Published:
February 20, 2010
Creative Commons License
Keywords:
precomputation search tree, obstacle rate, maximum size pruning, node selection strategy, steering set
Abstract
We present a new pruning method for compact precomputed search trees and evaluate the effectiveness and efficiency of our precomputation planning with steering sets. Precomputed search trees are one method for reducing planning time; however, there is a time-memory trade-off. Our PreComputed Search tree (PCS) is built with pruning based on a rule of constant memory, i.e., Maximum Size Pruning method (MSP), which is the preset pruning ratio. UsingMSP, we get a large, reasonably sized precomputed search tree. Applying a Node Selection Strategy (NSS) to MSP, extends the tree’s outer edges and enhances the path reachability. We also checked the dispersion in real 5150m2 indoor environments, we found the obstacle rate to be 5%. On the uniformed scattered obstacle map with a less than 13% obstacle rate, precomputation planning runtime with steering sets is more than two orders of magnitude faster than the planning without precomputed search trees. With steering sets, our precomputed search tree finds an optimal path at obstacle rate of 12%. Precomputation planning also produces a smooth optimal path speedily in an indoor environment.
Cite this article as:
Y. Suzuki, S. Thompson, and S. Kagami, “Effectiveness Evaluation of Precomputation Search Using Steering Sets,” J. Robot. Mechatron., Vol.22 No.1, pp. 112-121, 2010.
Data files:
References
  1. [1] N. Nilsson, “Principles of Artificial Intelligence,” Tioga Publishing Company, 1980.
  2. [2] J. J. Kuffner and S. M. LaValle, “Rrt-Connect: An Efficient Approach to Single-Query Path Planning,” In IEEE Int. Conf. on Robotics and Automation (ICRA’2000), pp. 995-1001, San Francisco, CA, April 2000.
  3. [3] A. Stentz, “Optimal and Efficient Path Planning for Partially-Known Environments,” In Proc. IEEE Int. Conf. on Robotics and Automation, May 1994.
  4. [4] L. Kavraki and J. C. Latombe, “Randomized Preprocessing of Configuration Space for Path Planning: Articu-Lated Robots,” In IEEE/RSJ/GI Int. Conf. on Intelligent Robots and Systems (IROS), pp. 1764-1772, 1994.
  5. [5] L. E. Kavraki and J. C. Latombe, “Randomized Preprocessing of Configuration Space for Fast Path Planning,” IEEE Press. San Diego, CA, pp. 2138-2139, 1994.
  6. [6] J. Go, T. Vu, and J. J. Kuffner, “Autonomous Behaviors for Interactive Vehicle Animations,” Int. J. of Graphical Models, 2005.
  7. [7] E. Frazzoli, M. A. Dahleh Y, and E. Feron, “Realtime Motion Planning for Agile Autonomous Vehicles,” AIAA J. of Guidance, Control, and Dynamics, Vol.25, pp. 116-129, 2002.
  8. [8] M. Lau and J. J. Kuffner, “Precomputed Search Trees: Planning for Interactive Goal-Driven Animation,” In 2006 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp. 299-308, Sep. 2006.
  9. [9] L. E. Dubins, “On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents,” American J. of Mathematics, Vol.79, No.3, pp. 497-516, Jul. 1957.
  10. [10] H. Chitsaz and S. M. LaValle, “Time-Optimal Paths for a Dubins Airplane,” In 2007 46th IEEE Conf. on Decision and Control, pp. 2379-2384. 2007 46th IEEE Conf. on Decision and Control, 12-14 Dec. 2007.
  11. [11] P. Garnier and T. Fraichard, “A Fuzzy Motion Controller for a Car-Like Vehicle,” In Proc. of the 1996 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems ’96 (IROS 96), Vol.3, pp. 1171-1178, Nov. 1996.
  12. [12] M. Yamamoto, M. Kobayashi, and A.Mohri, “Parking Motion Planning and Control of a Car-Like Robot Using a Fuzzy Neural Network,” J. of Robotics and Mechatronics, Vol.7, No.1, pp. 52-56, Dec. 1994.
  13. [13] A. Stentz, “The Focussed D* Algorithm for Real-Time Replanning,” In Proc. of Int. Joint Conf. on Artificial Intelligence, Aug. 1995.
  14. [14] A. Stentz andM. Herbert, “A Complete Navigation System for Goal Acquisition in Unknown Environments,” Autonomous Robots, Vol.2, No.2, pp. 127-145, 1995.
  15. [15] S. Koenig and M. Likhachev, “D* lite,” In Proc. of the National Conf. of Artificial Intelligence (AAAI), pp. 476-483, 2002.
  16. [16] Y. Suzuki, S. Kagami, and J. J. Kuffner, “Path Planning with Steering Set for Car-Like Robots and Finding an Effective Set,” In ROBIO, 2006 IEEE Int. Conf., 2006.
  17. [17] Y. Suzuki, S. Thompson, and S. Kagami, “Smooth Path Planning with Pedestrian Avoidance for Wheeled Robots: Implementation and Evaluation,” In Proc. of the 4th Int. Conf. on Autonomous Robots and Agents, pp. 657-662, Wellington, New Zealand, Feb. 2009.
  18. [18] M. Matsumoto and T. Nishimura, “Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator,” ACM Trans. Model. Comput. Simul., Vol.8, No.1, pp. 3-30, 1998.
  19. [19] M. Saito and M.Matsumoto, “Monte Carlo and Quasi-Monte Carlo Methods 2006,” Chapter 2, pp. 607-622. Springer Berlin Heidelberg, 2008.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

Copyright© 2010 by Fuji Technology Press Ltd. and Japan Society of Mechanical Engineers. All right reserved.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 18, 2024