JRM Vol.23 No.4 pp. 567-581
doi: 10.20965/jrm.2011.p0567


Building a Search Tree for a Pilot System of a Rescue Search Robot in a Discretized Random Step Environment

Evgeni Magid*, Takashi Tsubouchi*, Eiji Koyanagi**,
and Tomoaki Yoshida**

*Intelligent Robot Laboratory, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan

**Future Robotics Technology Center, Chiba Institute of Technology, 2-17-1 Tsudanuma, Narashino, Chiba 275-0016, Japan

October 25, 2010
March 4, 2011
August 20, 2011
rescue robot, USAR, random step environment

Rescue robotics applies search and rescue robots to expand rescue capabilities while increasing safety. Mobile robots working at a disaster site are monitored remotely by operators who may not be able to see the site well and select work paths appropriately. Our goal is to provide a “pilot system” that can propose options for traversing 3D debris environments. This requires a special debris path search algorithm and an appropriately defined search tree ensuring smooth exploration. To make a path search feasible in huge real state space we discretize search space and robot movement before a search. In this paper we present path quality estimation and search tree branching function F, which defines search tree building process online through node opening and branching. Well-defined function F removes unsuitable search directions from the search tree and enables dynamic path planning accounting for debris. Exhaustive simulation was used to structure and analyze data. Experiments confirmed the feasibility of our approach.

Cite this article as:
Evgeni Magid, Takashi Tsubouchi, Eiji Koyanagi, and
and Tomoaki Yoshida, “Building a Search Tree for a Pilot System of a Rescue Search Robot in a Discretized Random Step Environment,” J. Robot. Mechatron., Vol.23, No.4, pp. 567-581, 2011.
Data files:
  1. [1] J. Baltes and J. Anderson, “The Keystone Fire Brigade 2003,” AAAI Mobile Robot Competition Workshop, pp. 30-35, 2003.
  2. [2] K. Ohno, S. Morimura, S. Tadokoro, E. Koyanagi, and T. Yoshida, “Semi-autonomous Control System of Rescue Crawler Robot Having Flippers for Getting Over Unknown-Steps,” IEEE IROS, pp. 3012-3018, 2007.
  3. [3] J. Suthakorn, S. S. H. Shah, S. Jantarajit, W. Onprasert, W. Saensupo, S. Saeung, S. Nakdhamabhorn, V. Sa-Ing, and S. Reaungamornrat, “On the Design and Development of a Rough Terrain Robot for Rescue Missions,” IEEE ROBIO, pp. 1830-1835, 2008.
  4. [4] Y. Choi, K. Jeong, J. Kang, Y. Seo, S. Lee, S. Jung, and S. Kim, “A remotely operated mobile robot with modular track mechanisms,” ICCAS, pp. 1002-1005, 2007.
  5. [5] R. R. Murphy, “An Introduction to AI Robotics,” Cambridge, MA: The MIT Press, 2000.
  6. [6] T. Kimura,W. C. Vie, and Y. Ukai, “Development of a USAR Robot Considering Camera View Angle and Grouser Shape of Crawler,” IEEE ROBIO, pp. 1991-1994, 2009.
  7. [7] N. Midorikawa, K. Ohno, H. Kuwahara, and S. Tadokoro, “Development of Small-Size Multi Camera System for Snake-like Robot, and Display of Wide View-Angle Image,” IEEE SSRR, pp. 1-6, 2007.
  8. [8] O. Wulf, K. O. Arras, H. I. Christensen, and B. Wagner, “2D Mapping of Cluttered Indoor Environments by Means of 3D Perception,” IEEE ICRA, pp. 4204-4209, 2004.
  9. [9] Z. Zhang, H. Guo, G. Nejat, and P. Huang, “Finding Disaster Victims: A Sensory System for Robot-Assisted 3D Mapping of Urban Search and Rescue Environments,” IEEE ICRA, pp. 3889-3894, 2007.
  10. [10] M. Lewis and J. Wang, “Gravity-Referenced Attitude Display for Mobile Robots: Making Sense of What We See,” IEEE SMC, Part A: Systems and Humans, Vol.37, No.1, pp. 94-105, 2007.
  11. [11] K. Schilling and F. Driewer, “Remote Control of Mobile Robots for Emergencies,” 16th IFAC World Congress, 2005.
  12. [12] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, “Introduction to Algorithms (2nd Ed.),” The MIT Press and McGraw-Hil, 2001.
  13. [13] S. Russell and P. Norvig, “Artificial Intelligence: A Modern Approach (2nd Ed.),” Upper Saddle River, NJ: Prentice Hall, 2003.
  14. [14] A. Jacoff, E.Messina, and J. Evans, “Experiences in Deploying Test Arenas for Autonomous Mobile Robots,” Proc. PerMIS Workshop, 2001.
  15. [15] E. Magid, K. Ozawa, T. Tsubouchi, E. Koyanagi, and T. Yoshida, “Rescue Robot Navigation: Static Stability Estimation in Random Step Environment,” Proc. of SIMPAR, pp. 305-316, 2008.
  16. [16] E. Magid and T. Tsubouchi, “Static Balance for Rescue Robot Navigation: Translation Motion Discretization Issue within Random Step Environment,” Proc. of ICINCO, pp. 415-422, 2010.
  17. [17] E. Magid, T. Tsubouchi, E. Koyanagi, and T. Yoshida, “Static Balance for Rescue Robot Navigation: Losing Balance on Purpose within Random Step Environment,” IEEE IROS, pp. 349-356, 2010.
  18. [18] E. Magid and T. Tsubouchi, “Static Balance for Rescue Robot Navigation: Discretizing Rotational Motion within Random Step Environment,” Proc. of SIMPAR, pp. 423-435, 2010.
  19. [19] A. Jacoff, E. Messina, and J. Evans, “A standard test course for urban search and rescue robots,” Proc. PerMIS Workshop, pp. 499-503, 2000.
  20. [20] R. Sheh, M. W. Kadous, C. Sammut, and B. Hengst, “Extracting Terrain Features from Range Images for Autonomous Random Stepfield Traversal,” IEEE SSRR, pp. 1-6, 2007.
  21. [21] J.Wang, M. Lewis, and J. S. Gennari, “Interactive Simulation of the NIST USAR Arenas,” IEEE SMC, Vol.2, pp. 1327-1332, 2003.
  22. [22] J. Poppinga, A. Birk, and K. Pathak, “Hough Based Terrain Classification for Realtime Detection of Drivable Ground,” J. Field Robotics, Vol.25, No.1, pp. 67-88, 2008.
  23. [23] G. Ishigami, K. Nagatani, and K. Yoshida, “Path Planning for Planetary Exploration Rovers and Its Evaluation based on Wheel Slip Dynamics,” IEEE ICRA, pp. 2361-2366, 2007.
  24. [24] M. Cherif, J. Ibanez-Guzman, Ch. Laugier, and T. Goh, “Motion Planning for an All-Terrain Autonomous Vehicle,” Int. Conf. on Field and Service Robotics, 1999.
  25. [25] A. Chilian and H. Hirschmüller, “Stereo camera based navigation of mobile robots on rough terrain,” IEEE IROS, pp. 4571-4576, 2009.
  26. [26] B. Fontaine, D. Termont, L. Steinicke, M. Pollefeys, M. Vergauwen, R. Moreas, F. Xu, M. Steinmetz, B. Brunner, H. Michaelis, T. Behnke, R. Dequeker, P. Degezelle, R. Bertr, and G. Visentin, “Autonomous Operations of a Micro Rover for Geo Science on Mars,” Proc. 6th ESA workshop on advanced space technologies for robotics and automation, 2000.
  27. [27] M.-W. Kang, M. K. Jha, and G. Karri, “Determination of Robot Drop Locations for Military Path Planning Using GIS Application,” In Proc. of 4th WSEAS Int. Conf. on Computer Engineering and Applications, 2010.
  28. [28] C. Oh, B.-S. Choi, J.-J. Kim, J.-J. Lee, and H. J. Lee, “Modified A*algorithm for outdoor environments with risk and velocity map,” IEEE ISIE, pp. 1587-1591, 2009.
  29. [29] M. Arai, Y. Tanaka, S. Hirose, H. Kuwahara, and S. Tsukui, “Development of “Souryu-IV” and “Souryu-V”: Serially Connected Crawler Vehicles for In-rubble Searching Operations,” J. Field Robotics, Vol.25, No.1-2, pp. 31-65, 2008.
  30. [30] D. Campbell and M. Buehler, “Stair Descent in the Simple Hexapod RHex,” IEEE ICRA, pp. 1380-1385, 2003.
  31. [31] R. R. Murphy, S. Tadokoro, D. Nardi, A. Jacoff, P. Fiorini, H. Choset, and A. M. Erkmen, “Search and Rescue Robotics,” Springer Handbook of Robotics, pp. 1151-1173, 2008.
  32. [32] N. Sato, F.Matsuno, and N. Shiroma, “Development of a High Mobility Wheeled Rescue Robot with a 1-DOF Arm,” Int. J. of Advanced Mechatronic Systems, Vol.1, No.1, pp. 10-23, 2008.
  33. [33] J. Carlson and R. R. Murphy, “How UGVs Physically Fail in the Field,” IEEE Trans. on Robotics, Vol.21, No.3, pp. 423-437, 2005.
  34. [34] J. de Hoog, S. Cameron, and A. Visser, “Dynamic Team Hierarchies in Communication-Limited Multi-Robot Exploration,” IEEE SSRR, 2010.
  35. [35] K. Nagatani, N. Tokunaga, Y. Okada, and T. Yoshida, “Continuous Acquisition of Three-Dimensional Environment Information for Tracked Vehicles on Uneven Terrain,” IEEE SSRR, pp. 25-30, 2008.
  36. [36] K. Ohno and T. Yoshida, “Robot League Team “Pelican United (Japan)”,” RoboCup Rescue 2009, 2009.
  37. [37] T. Yoshida, K. Nagatani, E. Koyanagi, Y. Hada, K. Ohno, S. Maeyama, H. Akiyama, K. Yoshida, and S. Tadokoro, “Field Experiment on Multiple Mobile Robots Conducted in an Underground Mall,” Field and Service Robotics, Springer Tracts in Advanced Robotics, Vol.62, pp. 365-375, 2010.
  38. [38] E. Mihankhah, A. Kalantari, E. Aboosaeedan, H. D. Taghirad, S. Ali, and A. Moosavian, “Autonomous Staircase Detection and Stair Climbing for a Tracked Mobile Robot Using Fuzzy Controller,” IEEE ROBIO, pp. 1980-1985, 2009.
  39. [39] J. C. Latombe, “Robot Motion Planning,” Kluwer Academic Publishers, 1991.
  40. [40] I. Kamon, E. Rimon, and E. Rivlin, “Tangentbug: A Range-Sensor Based Navigation Algorithm,” J. of Robotics Research, Vol.17, No.9, pp. 934-953, 1998.
  41. [41] I. Kamon and E. Rivlin, “Sensory-Based Motion Planning with Global Proofs,” IEEE Trans. on Robotics and Automation, Vol.13, No.6, pp. 814-822, 1997.
  42. [42] T. Bretl and S. Lall, “A Fast and Adaptive Test of Static Equilibrium for Legged Robots,” IEEE ICRA, pp. 1109-1116, 2006.
  43. [43] D. W. Hong and R. J. Cipra, “Optimal Contact Force Distribution for Multi-limbed Robots,” J. of Mechanical Design, Vol.128, No.3, pp. 566-573, 2006.
  44. [44] C. A. Klein and S. Kittivatcharapong, “Optimal Force Distribution for the Legs of aWalking Machine with Friction Cone Constraints,” IEEE Trans. on Robotics and Automation, Vol.6, No.1, pp. 73-85, 1990.
  45. [45] R. Mason, E. Rimon, and J. Burdick, “Stable Poses of 3-dimensional Objects,” IEEE ICRA, Vol.1, pp. 391-398, 1997.
  46. [46] E. Garcia, J. Estremera, and P. G. de Santos, “A Classification of Stability Margins for Walking Robots,” Proc. of 5th CLAWAR, pp. 799-808, 2002.
  47. [47] D. A. Messuri, “Optimization of the Locomotion of a Legged Vehicle with Respect to Maneuverability,” Ph.D. Thesis, The Ohio State University, 1985.
  48. [48] S. Shoval, “Stability of aMulti Tracked Robot Traveling Over Steep Slopes,” IEEE ICRA, Vol.5, pp. 4701-4706, 2004.
  49. [49] M. Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf, “Computational Geometry: Algorithms and Applications,” Springer-Verlag, 2000.
  50. [50] S. Hirose, H. Tsukagoshi, and K. Yoneda, “Normalized Energy Stability Margin: Generalized Stability Criterion for Walking Vehicles,” Proc. of 1st CLAWAR, pp. 71-76, 1998.

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

Last updated on Mar. 05, 2021