Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-25T23:04:06.395Z Has data issue: false hasContentIssue false
  • English
  • Français

Offsetting obstacles of any shape for robot motion planning

Published online by Cambridge University Press:  19 March 2014

Md Nasir Uddin Laskar ,
Hoang Huu Viet ,
Seung Yoon Choi ,
Ishtiaq Ahmed ,
Sungyoung Lee  and
Tae Choong Chung
Md Nasir Uddin Laskar
Affiliation:
Artificial Intelligence Lab., Department of Computer Engineering, Kyung Hee University, Gyeonggi-do 446-701, South Korea
Hoang Huu Viet
Affiliation:
Department of Information Technology, Vinh University, 182-Le Duan, Vinh City, Nghe An, Vietnam
Seung Yoon Choi
Affiliation:
Artificial Intelligence Lab., Department of Computer Engineering, Kyung Hee University, Gyeonggi-do 446-701, South Korea
Ishtiaq Ahmed
Affiliation:
Artificial Intelligence Lab., Department of Computer Engineering, Kyung Hee University, Gyeonggi-do 446-701, South Korea
Sungyoung Lee
Affiliation:
Ubiquitous Computing Lab., Department of Computer Engineering, Kyung Hee University, Gyeonggi-do 446-701, South Korea
Tae Choong Chung*
Affiliation:
Artificial Intelligence Lab., Department of Computer Engineering, Kyung Hee University, Gyeonggi-do 446-701, South Korea
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

We present an algorithm for offsetting the workspace obstacles of a circular robot. Our method has two major steps: It finds the raw offset curve for both lines and circular arcs, and then removes the global invalid loops to find the final offset. To generate the raw offset curve and remove global invalid loops, O(n) and O((n+k)log m) computational times are needed respectively, where n is the number of vertices in the original polygon, k is the number of self-intersections and m is the number of segments in the raw offset curve, where m ≤ n. Any local invalid loops are removed before generating the raw offset curve by invoking a pair-wise intersection detection test (PIDT). In the PIDT, two intersecting entities are checked immediately after they are computed, and if the test is positive, portions of the intersecting segments are removed. Our method works for conventional polygons as well as the polygons that contain circular arcs. Our algorithm is simple and very fast, as each sub-process of the algorithm can be completed in linear time except the last one, which is nearly linear. Therefore, the overall complexity of the algorithm is nearly linear. By applying our simple and efficient approach, offsetting obstacles of any shape make it possible to construct a configuration space that ensures optimized motion planning.

Keywords

Mobile robotObstaclePolygon offsettingMotion planningConfiguration spaceGlobal invalid loop
Type
Articles
Information
Robotica , Volume 33 , Issue 4 , May 2015 , pp. 865 - 883
Copyright
Copyright © Cambridge University Press 2014 

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. Wein, R., Berg, J. P. and Halperin, D., “The Visibility-Voronoi Complex and Its Applications,” Proceedings of the Twenty-First Annual Symposium on Computational Geometry (SCG), Eindhoven, The Netherlands (2005) pp. 63–72.Google Scholar
2. Zhiwei, L., Jianzhong, F. and Wenfeng, G., “A robust 2d point-sequence curve offset algorithm with multiple islands for contour-parallel tool path,” Comput. Aided Des. 45, 657–660 (2013).Google Scholar
3. Choi, B. and Park, S., “A pair-wise offset algorithm for 2d point-sequence curve,” Comput Aided Des. 31, 735–745 (1999).Google Scholar
4. Wein, R., “Exact and approximate construction of offset polygons,” Comput. Aided Des. 39, 518–527 (2007).Google Scholar
5. Guibas, L. J. and Seidel, R., “Computing convolutions by reciprocal search,” Discrete Comput. Geom. 2, 175–193 (1987).Google Scholar
6. Milenkovic, V., Sacks, E. and Kyung, M.-H., “Robust Minkowski Sums of Polyhedra via Controlled Linear Perturbation,” ACM Symposium of Solid and Physical Modeling (SPM 10), Haifa, Israel (2010) pp. 23–30.Google Scholar
7. Wong, T. N. and Wong, K. W., “Toolpath generation for arbitrary pockets with islands,” Int. J. Adv. Manuf. Technol. 12, 174–179 (1996).Google Scholar
8. Kim, H.-C., “Tool path generation for contour parallel milling with incomplete mesh model,” Int. J. Adv. Manuf. Technol. 48, 443–454 (2010).Google Scholar
9. Kim, H.-C., Lee, S.-G. and Yang, M.-Y., “A new offset algorithm for closed 2d lines with islands,” Int. J. Adv. Manuf. Technol. 29, 1169–1177 (2006).Google Scholar
10. Bo, Q., “Recursive polygon offset computing for rapid prototyping applications based on Voronoi diagrams,” Int. J. Adv. Manuf. Technol. 49, 1019–1028 (2010).Google Scholar
11. Held, M., “Voronoi diagrams and offset curves of curvilinear polygons,” Comput. Aided Des. 30 (4), 287–300 (1998).CrossRefGoogle Scholar
12. Held, M. and Huber, S., “Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments,” Comput. Aided Des. 41, 327–338 (2009).Google Scholar
13. McMains, S., Smith, J., Wang, J. and Sequin, C., “Layered Manufacturing of Thin-Walled Parts,” Proceedings of ASME Design Engineering Technical Conference, Baltimore, MD (2000) pp. 343–356.Google Scholar
14. Chen, X. and McMains, S., “Polygon Offsetting by Computing Winding Numbers,” Proceedings of ASME International Design Engineering Technology Conference (IDETC), California, USA (2005) pp. 565–575.Google Scholar
15. Blomgren, R., “B-spline Curves,” In: Class Notes, Boeing Document B-7150-BB-WP-281/D-441.2, CASE/SME Seminar, Michigan, USA (1981).Google Scholar
16. Klass, R., “An offset spline approximation for plane cubic splines,” J. Comput. Aided Des. 15 (5), 297–299 (1983).Google Scholar
17. Esquivel, W. and Chaiang, L., “Nonholonomic path planning among obstacles subject to curvature restrictions,” Robotica 20 (1), 49–58 (2002).Google Scholar
18. Srivastava, A., Kartikey, D., Srivastava, U. and Rajesh, S., “Nonholonomic sortest robot path planning in a dynamic environment using polygonal obstacles,” Proceedings of International Conference on Industrial Technology (ICIT), Viña del Mar, Chile (2010) pp. 553–558.Google Scholar
19. Choset, H., “Coverage of known spaces: The boustrophedon cellular decomposition,” Int. J. Auton. Robots 9 (1), 247–253 (2000).Google Scholar
20. Viet, H. H., Dang, V.-H., Laskar, M. N. U. and Chung, T. C., “Ba*: An online complete coverage algorithm for cleaning robots,” Int. J. Appl. Intell. (2012) doi:10.1007/s10489-012-0406-4.Google Scholar
21. Schwartz, J. T. and Sharir, M., “On the piano movers problem: Ii. general techniques for computing topological properties of real algebraic manifolds,” Adv. Appl. Maths. 4, 298–351 (1983).Google Scholar
22. Berg, M., Cheong, O., Kreveld, M. and Overmars, M., Computational Geometry: Algorithms and Applications (Springer, New York, NY, 2008).CrossRefGoogle Scholar
23. LaValle, S. M., Planning Algorithms (Cambridge Univesity Press, Cambridge, UK, 2006).Google Scholar
24. Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E. and Thrun, S., Principles of Robot Motion (MIT Press, Cambridge, MA, 2007).Google Scholar
25. Clodic, A., Montreuil, V., Alami, R. and Chatila, R., “A Decisional Framework for Autonomous Robots Interacting with Humans,” Proceedings of the IEEE International Workshop on Robot Human Interaction Communication, Nashville, USA (2005) pp. 543–548.Google Scholar
26. Xu, B., Stilwell, D. and Kurdila, A., “A Receding Horizon Controller for Motion Planning in the Presence of Moving Obstacles,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Alaska, USA (2010) pp. 974–980.Google Scholar
27. Kedem, K. and Sharir, M., “An Automatic Motion Planning System for a Convex Polygonal Mobile Robot in 2D Polygonal Space,” ACM Symposium on Computational Geometry, Urbana-Champaign, IL (1998) pp. 329–340.Google Scholar
28. Varadhan, G., Krishnan, S., Sriram, T. V. and Manocha, D., “A simple algorithm for complete motion planning of translating polyhedral robots,” Int. J. Robot. Res. 24 (11), 983–995 (2005).Google Scholar
29. Sudsang, A., Rothganger, F. and Ponce, J., “Motion planning for disc-shaped robots pushing a polygonal object in the plane,” IEEE Trans. Robot. Autom. 18 (4), 550–562 (2002).Google Scholar
30. Bourke, P., “Intersection of two circles,” available at: http://paulbourke.net/geometry/circlesphere/ (1997) (accessed February 1, 2014).Google Scholar
31. Bentley, J. L. and Ottmann, T., “Algorithms for reporting and counting geometric intersections,” IEEE Trans. Comput. C-28 (9), 643–647 (1979).Google Scholar