Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T10:42:09.588Z Has data issue: false hasContentIssue false

A real-time motion planning algorithm for a hyper-redundant set of mechanisms

Published online by Cambridge University Press:  11 June 2013

Nir Shvalb*
Affiliation:
Mechanical Engineering, Ariel University, Ariel, Israel
Boaz Ben Moshe
Affiliation:
Computer Science, Ariel University, Ariel, Israel
Oded Medina
Affiliation:
Industrial Engineering, Ariel University, Ariel, Israel
*
*Corresponding author. E-mail: [email protected]

Summary

We introduce a novel probabilistic algorithm (CPRM) for real-time motion planning in the configuration space ${\EuScript C}$. Our algorithm differs from a probabilistic road map (PRM) algorithm in the motion between a pair of anchoring points (local planner) which takes place on the boundary of the obstacle subspace ${\EuScript O}$. We define a varying potential field f on ∂${\EuScript O}$ as a Morse function and follow $\vec{\nabla} f$. We then exemplify our algorithm on a redundant worm climbing robot with n degrees of freedom and compare our algorithm running results with those of the PRM.

Type
Articles
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Jianwen, Z., Lining, S., Zhijiang, D. and Bo, Z., “Self-Motion Analysis on a Redundant Robot with a Parallel/Series Hybrid Configuration,” In: Proceedings of the 9th International Conference on Control, Automation, Robotics and Vision (ICARCV), Singapore (Dec. 2006), pp. 16.Google Scholar
2.Brown, H., Schwerin, M., Shammas, E. and Choset, H., “Design and Control of a Second-Generation Hyper-Redundant Mechanism,” In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), San-Diego, California (2007) pp. 26032608.Google Scholar
3.Kornienko, S., Kornienko, O., Nagarathinam, A. and Levi, P., “From Real Robot Swarm to Evolutionary Multi-Robot Organism,” In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC), Singapore (2007) pp. 14831490.Google Scholar
4.Maruyama, H. and Ito, K., “Semi-Autonomous Snake-Like Robot for Search and Rescue,” In: Proceedings of the 2010 IEEE International Workshop on Safety Security and Rescue Robotics (SSRR), Bremen, Germany (Jul. 2010) pp. 16.Google Scholar
5.Ota, T., Degani, A., Schwartzman, D., Zubiate, B., McGarvey, J., Choset, H. and Zenati, M., “A highly articulated robotic surgical system for minimally invasive surgery,” Ann. Thoracic Surg. 87, 12531256 (May 2009).CrossRefGoogle ScholarPubMed
6.Yoon, H.-S. and Yi, B.-J., “A 4-dof Flexible Continuum Robot using a Spring Backbone,” In: Proceedings of the International Conference on Mechatronics and Automation (ICMA), Changchun, Jilin, China (Aug. 2009) pp. 12491254.Google Scholar
7.Xu, K. and Simaan, N., “Actuation Compensation for Flexible Surgical Snake-Like Robots with Redundant Remote Actuation,” In: Proceedings of the 2006 IEEE International Conference on Robotics and Automation (ICRA), Orlando, Florida (May 2006) pp. 41484154.Google Scholar
8.Akhtaruzzaman, M. and Shafie, A., “Evolution of Humanoid Robot and Contribution of Various Countries in Advancing the Research and Development of the Platform,” In: Proceedings of the 2010 International Conference on Control Automation and Systems (ICCAS), Gyeonggi-do, Korea (Oct. 2010) pp. 10211028.Google Scholar
9.Siciliano, B. and Khatib, O., Springer Handbook of Robotics (Springer-Verlag, New York, 2008).CrossRefGoogle Scholar
10.Kuffner, J., Nishiwaki, K., Kagami, S., Inaba, M. and Inoue, H., “Motion planning for humanoid robots,” Robot. Res., 21 (1), 365374 (2005).Google Scholar
11.Yagnik, D., Ren, J. and Liscano, R., “Motion Planning for Multi-Link Robots Using Artificial Potential Fields and Modified Simulated Annealing,” In: Proceedings of 2010 IEEE/ASME International Conference on Mechatronics and Embedded Systems and Applications (MESA), Vancouver, Canada (Jul. 2010) pp. 421427.Google Scholar
12.Masoud, A., “A Discrete Harmonic Potential Field for Optimum Point-to-Point Routing on a Weighted Graph,” In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, Caina (Oct. 2006), pp. 17791784.Google Scholar
13.Khanmohammadi, S. and Mahdizadeh, A., “Density Avoided Sampling: An Intelligent Sampling Technique for Rapidly-Exploring Random Trees,” In: Proceedings of the 8th International Conference on Hybrid Intelligent Systems, 2008 (HIS '08), Barcelona, Spain (Sep. 2008), pp. 672677.Google Scholar
14.Kavraki, L., Latombe, J., Motwani, R. and Raghavan, P., “Randomized Query Processing in Robot Path Planning,” In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, Las Vegas, Nevada (1995) pp. 353362.Google Scholar
15.Medina, O., Taitz, A., Moshe, B. B., and Shvalb, N., “C-space compression for robots motion planning,” Int. J. Adv. Robotic. Syst. 10 (6), 17 (2013).Google Scholar
16.Rimon, E. and Koditschek, D., “Exact robot navigation using artificial potential functions,” IEEE Trans. Robot. Autom. 8 (5), 501518 (1992).CrossRefGoogle Scholar
17.Ni, X., Garland, M. and Hart, J., “Fair morse functions for extracting the topological structure of a surface mesh,” ACM Trans. Graph. 23 (3)613622 (2004).CrossRefGoogle Scholar
18.Milnor, J., Morse Theory (Princeton University Press, NJ, 1963).CrossRefGoogle Scholar
19.Plaku, E., Bekris, K., Chen, B., Ladd, A. and Kavraki, L., “Sampling-based roadmap of trees for parallel motion planning,” IEEE Trans. Robot. 21 (4), 597608 (2005).CrossRefGoogle Scholar
20.Bleiweiss, A., “GPU Accelerated Pathfinding,” In: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware, Eurographics Association, Sarajevo, Bosnia (2008) pp. 6574.Google Scholar
21.Kider, J., Henderson, M., Likhachev, M. and Safonova, A., “High-Dimensional Planning on the GPU,” In: Proceedings of 2010 IEEE International Conference on Robotics and Automation (ICRA), Anchorage, Alaska (2010) pp. 25152522.CrossRefGoogle Scholar
22.Atramentov, A. and LaValle, S., “Efficient Nearest Neighbor Searching for Motion Planning,” In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Vol. 1, IEEE, Washington, D.C. (2002) pp. 632637.Google Scholar
23.Yershova, A. and LaValle, S., “Improving motion-planning algorithms by efficient nearest-neighbor searching,” IEEE Trans. Robot. 23 (1), 151157 (2007).CrossRefGoogle Scholar