Làm Mềm Đường Đi Liên Tục Cho Robot Giống Như Ô Tô Sử Dụng Đường Cong B-Spline

Journal of Intelligent and Robotic Systems - Tập 80 - Trang 23-56 - 2015
Mohamed Elbanhawi1, Milan Simic1, Reza N. Jazar1
1School of Aerospace, Mechanical, and Manufacturing Engineering (SAMME), RMIT University.Bundoora East Campus, Melbourne, Australia

Tóm tắt

Một phương pháp thực tiễn để tạo ra các đường đi với sự điều khiển liên tục cho các robot di động dạng ô tô được trình bày ở đây. Bài báo giải quyết hai vấn đề chính trong lập kế hoạch chuyển động của robot: tính liên tục của đường đi và ràng buộc độ cong tối đa đối với các robot không holonomic. Ưu điểm của phương pháp mới này là nó cho phép robot tính toán các ràng buộc của chúng một cách hiệu quả, tạo điều kiện cho việc lập kế hoạch theo thời gian thực. Các đường cong B-spline được tận dụng vì tính bền vững và khả năng tổng hợp thực tiễn để mô hình hóa đường đi của phương tiện. Các phân tích dựa trên điều hướng so sánh được trình bày để chọn đường cong phù hợp và đề xuất các tham số của nó. Tính liên tục của đường đi được đạt được bằng cách sử dụng một đường dẫn duy nhất để đại diện cho quỹ đạo, mà không có giới hạn về đường đi hoặc định hướng. Các tham số của đường đi được hình thành theo các ràng buộc của robot. Độ cong tối đa được thỏa mãn một cách cục bộ, trong mỗi đoạn sử dụng một thuật toán làm mịn, nếu cần thiết. Được chứng minh rằng bất kỳ thay đổi cục bộ nào của các đoạn đơn lẻ có ảnh hưởng tối thiểu đến toàn bộ đường đi. Các mô phỏng nghiêm ngặt được trình bày để làm nổi bật các lợi ích của phương pháp đề xuất, so với các phương pháp hiện có liên quan đến tính liên tục, kiểm soát độ cong, chiều dài đường đi và gia tốc kết quả. Kết quả thực nghiệm xác thực rằng phương pháp của chúng tôi bắt chước việc điều khiển của con người với độ chính xác cao. Do vậy, việc thiết lập những đường đi liên tục được lập trình một cách hiệu quả cuối cùng góp phần cải thiện sự thoải mái cho hành khách. Bằng cách sử dụng phương pháp được trình bày, các phương tiện tự trị tạo ra và theo dõi các con đường mà con người đã quen thuộc, với sự quấy rầy tối thiểu.

Từ khóa

#robot di động #đường đi liên tục #đường cong B-spline #lập kế hoạch chuyển động #ô tô tự lái

Tài liệu tham khảo

Reif, J.H.: Complexity of the mover’s problem and generalizations. In: Foundations of Computer Science, 1979., 20th Annual Symposium on, pp. 421–427 (1979)

Latombe, J.-C.: Motion Planning: A journey of robots, molecules, digital actors, and other artifacts. Int. J. Robot. Res. 18(11), 1119–1128 (1999). doi:10.1177/02783649922067753

Choset, H.M.: Principles of Robot Motion, Theory, Algorithms, and Implementation. Prentice Hall of India (2005)

Brooks, R.A., Lozano-Perez, T.: A subdivision algorithm in configuration space for findpath with rotation. IEEE Trans. Syst. Man Cybern. 15(2), 224–233 (1985). doi:10.1109/TSMC.1985.6313352

Canny, J.: A Voronoi method for the piano-movers problem. In: Robotics and Automation. Proceedings. 1985 IEEE International Conference on, pp. 530–535 (1985)

Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res. 5(1), 90–98 (1986). doi:10.1177/027836498600500106

Arkin, R.C.: Motor Schema Based Mobile Robot Navigation. Int. J. Robot. Res. 8(4), 92–112 (1989). doi:10.1177/027836498900800406

Koren, Y., Borenstein, J.: Potential field methods and their inherent limitations for mobile robot navigation. In: Robotics and Automation, 1991. Proceedings., 1991 IEEE International Conference on, vol. 1392, pp. 1398–1404 (1991)

Elbanhawi, M., Simic, M.: Sampling-based robot motion planning: a review. IEEE Access 2, 56–77 (2014). doi:10.1109/ACCESS.2014.2302442

Geraerts, R., Overmars, M.H.: Creating high-quality paths for motion planning. Int. J. Robot. Res. 26(8), 845–863 (2007). doi:10.1177/0278364907079280

Laumond, J.P., Sekhavat, S., Lamiraux, F.: Guidelines in nonholonomic motion planning for mobile robots. In: J.P. Laumond (ed.) Robot Motion Planning and Control, vol. 229. Lecture Notes in Control and Information Sciences, pp. 1–53. Springer Berlin Heidelberg (1998)

Cheng, P.: Sampling-based motion planning with differential constraints. Ph.D. University of Illinois at Urbana-Champaign (2005)

Wallace, R., Stentz, A., Thorpe, C., Moravec, H., Whittaker, W., Kanade, T.: First Results in Robot Road Following. In: 1985, pp. 381–387

Antonelli, G., Chiaverini, S., Fusco, G.: A fuzzy-logic-based approach for mobile robot path tracking. IEEE Trans. Fuzzy Syst. 15(2), 211–221 (2007)

Perez, J., Milanes, V., Onieva, E.: Cascade architecture for lateral control in autonomous vehicles. IEEE Intell. Transp. Syst. 12(1), 73–82 (2011). doi:10.1109/TITS.2010.2060722

Jazar, R.N.: Mathematical theory of autodriver for autonomous vehicles. J. Vib. Control. 16(2), 253–279 (2010)

Marzbani, H., Ahmad Salahuddin, M.H., Simic, M., Fard, M., Jazar, R.N.: Steady-state dynamic steering. In: Frontiers in Artificial Intelligence and Applications, vol. 262 (2014)

Cheein, F.A., Scaglia, G.: Trajectory Tracking Controller Design for Unmanned Vehicles: A New Methodology. Journal of Field Robotics, n/a-n/a. doi:10.1002/rob.21492 (2013)

Magid, E., Keren, D., Rivlin, E., Yavneh, I.: Spline-Based Robot Navigation. In: Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on, pp. 2296–2301 (2006)

Roth, S., Batavia, P.: Evaluating Path Tracker Performance for Outdoor Mobile Robots. Paper presented at the Automation Technology for Off-Road Equipment, Chicago, Illinois, USA, 26–27/07

Lau, B., Sprunk, C., Burgard, W.: Kinodynamic motion planning for mobile robots using splines. In: Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on, pp. 2427–2433 (2009)

Gulati, S., Kuipers, B.: High performance control for graceful motion of an intelligent wheelchair. In: Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on, pp. 3932–3938 (2008)

Berglund, T., Brodnik, A., Jonsson, H., Staffanson, M., Soderkvist, I.: Planning smooth and obstacle-avoiding b-spline paths for autonomous mining vehicles. IEEE Trans. Autom. Sci. Eng. 71), 167–172 (2010). doi:10.1109/TASE.2009.2015886

Maekawa, T., Noda, T., Tamura, S., Ozaki, T., Machida, K.-i.: Curvature continuous path generation for autonomous vehicle using B-spline curves. Comput. Aided Des. 42(4), 350–359 (2010) doi:10.1016/j.cad.2009.12.007

Sabelhaus, D., Röben, F., Meyer zu Helligen, L.P., Schulze Lammers, P.: Using continuous-curvature paths to generate feasible headland turn manoeuvres. Biosyst. Eng. 116(4), 399–409 (2013). doi:10.1016/j.biosystemseng.2013.08.012

Girbés, V., Armesto, L., Tornero, J.: Path following hybrid control for vehicle stability applied to industrial forklifts. Robot. Auton. Syst. 0 (2014). doi:10.1016/j.robot.2014.01.004

Xuan-Nam, B., Boissonnat, J.-d., Soueres, P., Laumond, J.P.: Shortest path synthesis for Dubins non-holonomic robot. In: Robotics and Automation, 1994. Proceedings., 1994 IEEE International Conference on, 8–13 1994, Vol. 1, pp. 2–7

Anderson, E.P., Beard, R.W., McLain, T.W.: Real-time dynamic trajectory smoothing for unmanned air vehicles. IEEE Trans. Control Syst. Technol. 13(3), 471–477 (2005). doi:10.1109/TCST.2004.839555

Myung, H., Kuffner, J., Kanade, T.: Efficient Two-phase 3D Motion Planning for Small Fixed-wing UAVs. In: Robotics and Automation, 2007 IEEE International Conference on, pp. 1035–1041 (2007)

LaValle, S.: Planning Algorithms. Cambridge University Press (2006)

Suzuki, Y., Kagami, S., Kuffner, J.J.: Path Planning with Steering Sets for Car-Like Robots and Finding an Effective Set. In: Robotics and Biomimetics, 2006. ROBIO ’06. IEEE International Conference on, pp. 1221–1226 (2006)

Pivtoraiko, M., Knepper, R.A., Kelly, A.: Differentially constrained mobile robot motion planning in state lattices. J. Field Robot. 26(3), 308–333 (2009)

Fraichard, T., Scheuer, A.: From Reeds and Shepp’s to continuous-curvature paths. Robot. IEEE Trans. 20(6), 1025–1035 (2004). doi:10.1109/TRO.2004.833789

Wang, L.Z., Miura, K.T., Nakamae, E., Yamamoto, T., Wang, T.J.: An approximation approach of the clothoid curve defined in the interval [0, π/2] and its offset by free-form curves. Comput. Aided Des. 33(14), 1049–1058 (2001). doi:10.1016/S0010-4485(00)00142-1

Meek, D.S., Walton, D.J.: An arc spline approximation to a clothoid. J. Comput. Appl. Math. 170(1), 59–77 (2004) doi:10.1016/j.cam.2003.12.038

Montes, N., Herraez, A., Armesto, L., Tornero, J.: Real-time clothoid approximation by Rational Bezier curves. In: In: Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on, pp. 2246–2251 (2008)

McCrae, J., Singh, K.: Sketching piecewise clothoid curves. Comput. Graph. 33(4), 452–461 (2009) doi:10.1016/j.cag.2009.05.006

Brezak, M., Petrovic, I.: Real-time approximation of clothoids with bounded error for path planning applications. IEEE Trans. Robot. PP(99), 1–9 (2013). doi:10.1109/TRO.2013.2283928

Farin, G.: From conics to NURBS: A tutorial and survey. IEEE Comput. Graph. Appl. 12(5), 78–86 (1992). doi:10.1109/38.156017

Piegl, L.: On NURBS: a survey. IEEE Comput. Graph. Appl. 11(1), 55–71 (1991). doi:10.1109/38.67702

Farin, G.: Curves and Surfaces for CAGD. Computing. Morgan Kaufmann (2002)

Lepetič, M., Klančar, G., Škrjanc, I., Matko, D., Potočnik, B.: Time optimal path planning considering acceleration limits. Robot. Auton. Syst. 45(3–4), 199–210 (2003). doi:10.1016/j.robot.2003.09.007

Jolly, K.G., Sreerama Kumar, R., Vijayakumar, R.: A Bezier curve based path planning in a multi-agent robot soccer system without violating the acceleration limits. Robot. Auton. Syst. 57(1), 23–33 (2009). doi:10.1016/j.robot.2008.03.009

Schoenberg, I.J.: Contributions to the problem of approximation of equidistant data by analytic functions - b. on the problem of osculatory interpolation - a 2nd class of approximation formulae. Q. Appl. Math. 4(2), 112–141 (1946)

Thompson, S.E., Patel, R.V.: Formulation of joint trajectories for industrial robots using b-splines. IEEE Trans. Ind. Electron. 34(2), 192–199 (1987). doi:10.1109/TIE.1987.350954

Dyllong, E., Visioli, A.: Planning and real-time modifications of a trajectory using spline techniques. Robotica 21(05), 475–482 (2003). doi:10.1017/S0263574703005009

Hodgins, J.K., O’Brien, J.F., Tumblin, J.: Perception of human motion with different geometric models. IEEE Trans. Vis. Comput. Graph. 4(4), 307–316 (1998). doi:10.1109/2945.765325

Schmid, A.J., Woern, H.: Path planning for a humanoid using NURBS curves. In: Automation Science and Engineering, 2005. IEEE international conference on, pp. 351–356 (2005)

Sungchul, J., Taehoon, K.: Tool-path generation for NURBS surface machining. In: American control conference, 2003. Proceedings of the 200, Vol. 2613, pp. 2614–2619 (2003)

Cheng, M.Y., Kuo, J.C.: Real-time NURBS command generators for CNC servo controllers. Int. J. Mach. Tools Manuf. 42(7), 801–813 (2002) doi:10.1016/S0890-6955(02)00015-9

Zhang, Y., Bazilevs, Y., Goswami, S., Bajaj, C.L., Hughes, T.J.R.: Patient-specific vascular NURBS modeling for isogeometric analysis of blood flow. Comput. Methods Appl. Mech. Eng. 196(29–30), 2943–2959 (2007). doi:10.1016/j.cma.2007.02.009

Ma, W., Kruth, J.P.: NURBS curve and surface fitting for reverse engineering. Int. J. Adv. Manuf. Technol. 14(12), 918–927 (1998). doi:10.1007/BF01179082

Piegl, L.A., Tiller, W.: Parametrization for surface fitting in reverse engineering. Comput. Aided Des. 33(8), 593–603 (2001). doi:10.1016/S0010-4485(00)00103-2

Hughes, T.J.R., Reali, A., Sangalli, G.: Duality and unified analysis of discrete approximations in structural dynamics and wave propagation: Comparison of p-method finite elements with k-method NURBS. Comput. Methods Appl. Mech. Eng. 197(49–50), 4104–4124 (2008). doi:10.1016/j.cma.2008.04.006

Koyuncu, E., Inalhan, G.: A probabilistic B-spline motion planning algorithm for unmanned helicopters flying in dense 3D environments. In: Intelligent Robots and Systems, 2008. IROS 2008. IEEE/RSJ International Conference on, pp. 815–821 (2008)

Zhou, F., Song, B., Tian, G.: Bézier curve based smooth path planning for mobile robot. J. Inf. Comput. Sci. 8(12), 2441–2450 (2011)

Kwangjin, Y., Sukkarieh, S.: An analytical continuous-curvature path-smoothing algorithm. Robot. IEEE Trans. 26(3), 561–568 (2010). doi:10.1109/TRO.2010.2042990

Kwangjin, Y., Jung, D., Sukkarieh, S.: Continuous curvature path-smoothing algorithm using cubic Bezier spiral curves for non-holonomic robots. Adv. Robot. 27(4), 247–258 (2013). doi:10.1080/01691864.2013.755246

Walton, D.J., Meek, D.S., Ali, J.M.: Planar G2 transition curves composed of cubic Bézier spiral segments. J. Comput. Appl. Math. 157(2), 453–476 (2003). doi:10.1016/s0377-0427(03)00435-7

Huh, U.-Y., Chang, S.-R.: A G 2 continuous path-smoothing algorithm using modified quadratic polynomial interpolation. Int. J. Adv. Robot. Syst. 25(11) (2014). doi:10.5772/57340

Piazzi, A., Bianco, C.G.L., Romano, M.: η3-Splines for the smooth path generation of wheeled mobile robots. robotics-splines for the smooth path generation of wheeled mobile robots. Robot. IEEE Trans. 23(5), 1089–1095 (2007). doi:10.1109/TRO.2007.903816

Pan, J., Zhang, L., Manocha, D.: Collision-free and smooth trajectory computation in cluttered environments. Int. J. Robot. Res. 31(10), 1155–1175 (2012). doi:10.1177/0278364912453186

Nikolos, I.K., Valavanis, K.P., Tsourveloudis, N.C., Kostaras, A.N.: Evolutionary algorithm based offline/online path planner for UAV navigation. Systems, Man, and Cybernetics, Part B. Cybern. IEEE Trans. 33(6), 898–912 (2003). doi:10.1109/TSMCB.2002.804370

Guarino Lo Bianco, C.: Minimum-jerk velocity planning for mobile robot applications. Robot. IEEE Trans. 29(5), 1317–1326 (2013). doi:10.1109/TRO.2013.2262744

Kunz, T., Stilman, M.: Time-optimal trajectory generation for path following with bounded acceleration and velocity. Robotics: Science and Systems, p 209 (2013)

Velenis, E., Tsiotras, P.: Minimum-time travel for a vehicle with acceleration limits: theoretical analysis and receding-horizon implementation. J. Optim. Theory Appl. 138(2), 275–296 (2008). doi:10.1007/s10957-008-9381-7

Johnson, J., Hauser, K.: Optimal acceleration-bounded trajectory planning in dynamic environments along a specified path. In: Robotics and Automation (ICRA), 2012 IEEE International Conference on, pp. 2035–2041 (2012)

Elbanhawi, M., Simic, M., Jazar, R.: Continuous-curvature bounded trajectory planning using parametric splines. In: Frontiers in Artificial Intelligence and Applications, vol. 262, pp. 513–522 (2014)

Kelly, A., Stentz, A.: Rough terrain autonomous mobility—part 1: A theoretical analysis of requirements. Auton. Robot. 2(5), 129–161 (1998). doi:10.1023/A:1008801421636

Ahmed, F., Deb, K.: Multi-objective path planning using spline representation. In: Robotics and Biomimetics (ROBIO), 2011 IEEE International Conference on, pp. 1047–1052 (2011)

De Boor, C.: On calculating with B-splines. J. Appro. Theory 6(1), 50–62 (1972)

Barsky, B.A., Derose, T.D.: Geometric continuity of parametric curves: constructions of geometrically continuous splines. IEEE Comput. Graph. Appl. 10(1), 60–68 (1990). doi:10.1109/38.45811

Jan, G.E., Sun, C.C., Tsai, W.C., Lin, T.H.: An O(n log n) Shortest Path Algorithm Based on Delaunay Triangulation, Mechatronics. IEEE/ASME Trans. PP(99), 1–7 (2013). doi:10.1109/TMECH.2013.2252076

Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., Thrun, S.: Anytime search in dynamic graphs. Artif. Intell. 172(14), 1613–1643 (2008). doi:10.1016/j.artint.2007.11.009

Bruce, J.R., Veloso, M.M.: Safe multirobot navigation within dynamics constraints. IEEE Proc. 94(7), 1398–1411 (2006). doi:10.1109/JPROC.2006.876915

LaValle, S.M.: Planning Algorithms. Cambridge University Press (2006)

LaValle, S.M.: Rapidly-exploring random trees: A new tool for path planning. In. Iowa state university (1998)

Wein, R., van den Berg, J., Halperin, D.: Planning high-quality paths and corridors amidst obstacles. Int. J. Robot. Res. 27(11-12), 1213–1231 (2008). doi:10.1177/0278364908097213

Thông tin
Thông tin xuất bản

Journal of Intelligent and Robotic Systems

Tập 80

23-56

Thông tin tác giả