A fuzzy-tabu real time controller for sampling-based motion planning in unknown environment
Tóm tắt
Sampling-based path planning methods for autonomous agents are one of the well-known classes of robotic navigation approaches with significant advantages including ease of implementation and efficiency in problems with high degrees of freedom. However, there are some serious drawbacks like inability to plan in unknown environments, failure in complex workspaces, instability of results in different runs, and generating non-optimal solutions; which make sampling-based planners less efficient in practice. In this paper, a fuzzy controller is proposed which utilizes the heuristic rules of Tabu search to improve the quality of generated samples. The main contribution of this work is the ability of the proposed sampling-based planner to work effectively in unknown environments and to plan efficiently in complex workspaces by letting the fuzzy-Tabu controller check the quality of the generated samples before any further processing. The efficiency of the proposed planner is tested in several workspaces and the comparison studies show significant improvement in runtime and failure rate. Furthermore, the decision variables of the proposed controller are discussed in detail to determine their effect on the performance of the algorithm.
Tài liệu tham khảo
Canny J (1988) The complexity of robot motion planning. The MIT Press, Massachusetts
Asano T, Asano T, Guibas L, Hershberger J, Imai H (1985) Visibility-polygon search and Euclidean shortest paths. In: Proceedings of 26th Annual Symposium on Foundations of Computer Science, Oct 21-23, Portland, USA, 155-164
Canny J (1985) Voronoi method for the piano-mover’s problem. In: Proceedings of IEEE International Conference on Robotics and Automation. Mar 25-28, St. Louis, USA, pp 530-535
Khatib O (1986) Real-Time Obstacle Avoidance for Manipulators and Mobile Robots. Int J Rob Res 5:90–99. doi:10.1177/027836498600500106
Lumelsky VJ, Stepanov AA (1987) Path-planning strategies for a point mobile automaton moving amidst unknown obstacles for arbitrary shape. Algorithmica 2:403–430. doi:10.1007/BF01840369
Khaksar W, Tang SH, Khaksar M, Motlagh O (2013) A Low Dispersion Probabilistic Roadmaps (LD-PRM) Algorithm for Fast and Efficient Sampling-Based Motion Planning. Int J Adv Robot Syst 10:397. doi:10.5772/56973
Ryan MRK (2008) Exploiting Subgraph Structure in Multi-Robot Path Planning. J Artif Intell Res 31:497–542. doi:10.1613/jair.2408
Nash A, Koenig S, Felner A, Daniel K (2010) Theta*: Any-Angle Path Planning on Grids. J Artif Intell Res 39:533–579. doi:10.1613/jair.2994
Tang SH, Khaksar W, Ismail NB, Ariffin MK A (2012) A Review on Robot Motion Planning Approaches. Pertanika J Sci & Technol 20:15–29
Khaksar W, Tang SH, Khaksar M, Motlagh O (2012) Sampling-Based Tabu Search Approach for Online Path Planning. Adv Robot 26:1013–1034. doi:10.1163/156855312X632166
Hoang HV, Viet-Hung D, Md Nasir UL, TaeChoong C (2013) BA*: an online complete coverage algorithm for cleaning robots. Appl Intell 39:217–235. doi:10.1007/s10489-012-0406-4
Kala R, Warwick K (2014) Dynamic distributed lanes: motion planning for multiple autonomous vehicles. Appl Intell. doi:10.1007/s10489-014-0517-1
Kawraki LE, Svestka P, Latombe JC, Overmars MH (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans Robot Autom 12:566–580. doi:10.1109/70.508439
Lavalle SM (1998) Rapidly-exploring random trees: A new tool for path planning. Technical Report TR 98-11, Computer Science Department, Iowa State University
Karaman S (2013) Sampling-based algorithms for optimal motion planning. Int J Rob Res 30:846–894. doi:10.1177/0278364911406761
Lavalle SM (2006) Planning Algorithms. Cambridge University Press, Cambridge
Choset H, Lynch KM, Hutchinson S, Kantor G, Burgard W, Kavraki LE, Thrun S (2005) Principles of robot motion-theory: algorithms, and implementation. MIT Press, Cambridge
Boor V, Overmars MH, Van der Stappen AF (1999) The Gaussian sampling strategy for probabilistic roadmap planners. In:Proceedings of IEEE International Conference on Robotics and Automation, May 10-15, Detroit, USA, pp 1018–1023
Branicky MS, LaValle SM, Olson K, Libo Y, Quasi-randomized path planning Proceedings of IEEE International Conference on Robotics and Automation. May 21-26 COEX Seoul Korea (2001)
Kurniawati H, Hsu D (2004) Workspace importance sampling for probabilistic roadmap planning. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sep 28-Oct 2. Sendai, Japan, pp 1618–1623
Hsu D, Sanchez-Ante G, Zheng S (2005) Hybrid PRM Sampling with a Cost-Sensitive Adaptive Strategy. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA). Aug 2-6. Alberta, Canada, pp 3874–3880
Hsu D, Tingting J, Reif J, Zheng S (2003) The bridge test for sampling narrow passages with probabilistic roadmap planners. In Proceedings of IEEE International Conference on Robotics and Automation (ICRA), Oct, Las Vegas, Nevada, pp 4420–4426
Yershova KA, Jaillet L, Simoen T, LaValle SM (2005) Dynamic Domain RRTs: Efficient exploration by controlling the sampling domain. In: Proceedings of IEEE International Conference on Robotics and Automation, April, Barcelona, Spain, pp 3856-3861
Jaillet L, Yershova A, LaValle SM, Simeon T (2005) Adaptive tuning of the sampling domain for Dynamic-Domain RRTs. In: Proceedings of IEEE International Conference on Robotics and Automation, April, Barcelona, Spain, pp 2851-2856
Ferguson D, Kalra N, Stentz A (2006) Replanning with RRTs. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 1243-1248
Bruce J, Veloso M (2002) Real-time randomized path planning for robot navigation. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. pp 2383-2388
BekrisK E, Kavraki LE (2007) Greedy but Safe Replanning under Kinodynamic Constraints. In: Proceedings of IEEE International Conference on Robotics and Automation, Roma, Italy, 704-710
Glover F (1989) Tabu Search-Part I. ORSA J on Comput 1:190–206. doi:10.1287/ijoc.1.3.190
Glover F (1990) Tabu Search-Part II. ORSA J on Comput 2:4–32. doi:10.1287/ijoc.1.3.190
Whitley LD, Howe AE, Watson JP (2004) Linking Search Space Structure, Run-Time Dynamics, and Problem Difficulty: A Step Toward Demystifying Tabu Search. J Artif Intell Res 24:221–261. doi:10.1613/jair.1576
Masehian E, Amin-Naseri MR (2008) Sensor-based robot motion planning - A Tabu search approach. IEEE Robot & Autom Mag 15:48–57. doi:10.1109/MRA.2008.921543
Hedar AR, Ali AF (2012) Tabu search with multi-level neighborhood structures for high dimensional problems. Appl Intell 37:189–206. doi:10.1007/s10489-011-0321-0
Salt SM, Arafeh AM (2014) Cell assignment in hybrid CMOS/nanodevices architecture using Tabu Search. Appl Intell 40:1–12. doi:10.1007/s10489-013-0441-9
Hong TL, Sheu HC, HE YK (2002) Multicriteria scheduling using fuzzy theory and tabu search. Int J Prod Res 40:1221–1234. doi:10.1080/00207540110098832
Li C, Liao X, Yu J (2004) Tabu search for fuzzy optimization and applications. Inform Sci 158:3–13. doi:10.1016/j.ins.2003.07.015
Zheng Y (2010) Extended tabu search on fuzzy traveling salesman problem in multi-criteria analysis. In: Chen B (ed) Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, pp 314–324
Talbi N, Belarbi K (2011) Optimization of fuzzy controller using tabu search and particle swarm optimization. In: International Conference on Hybrid Intelligent Systems (HIS). Dec 5–8, Malaca, Malaysia, pp 561–565
Bjork KM, Mezei J (2013) A fuzzy tabu search approach to solve a vehicle routing problem. In: Hutchison D (ed) Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, pp 210–217