Maximizing the coverage of roadmap graph for optimal motion planning. (English) Zbl 1407.93266
Summary: Automated motion-planning technologies for industrial robots are critical for their application to Industry 4.0. Various sampling-based methods have been studied to generate the collision-free motion of articulated industrial robots. Such sampling-based methods provide efficient solutions to complex planning problems, but their limitations hinder the attainment of optimal results. This paper considers a method to obtain the optimal results in the roadmap algorithm that is representative of the sampling-based method. We define the coverage of a graph as a performance index of its optimality as constructed by a sampling-based algorithm and propose an optimization algorithm that can maximize graph coverage in the configuration space. The proposed method was applied to the model of an industrial robot, and the results of the simulation confirm that the roadmap graph obtained by the proposed algorithm can generate results of satisfactory quality in path-finding tests under various conditions.
MSC:
| 93C85 | Automated systems (robots, etc.) in control theory |
| 68T40 | Artificial intelligence for robotics |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
References:
| [1] | Latombe, J. C., Robot Motion Planning (1991), Kluwer Academic Publishers · doi:10.1177/027836499201100412 |
| [2] | Cheset, H.; Lynch, K. M.; Hutchinson, S.; Kantor, G.; Burgard, W.; Kavraki, L. E.; Thrun, S., Principles of Robot Motion: Theory, Algorithms, and Implementations (2005), Cambridge, UK: The MIT Press, Cambridge, UK · Zbl 1081.68700 |
| [3] | Kavaraki, L. E.; Svestka, P.; Latmobe, J. C.; Overmars, M. H., Probabilistic roadmaps for path planning in high-dimensional configuration space, IEEE Transactions on Robotics and Automation, 12, 4, 566-580 (1996) |
| [4] | Barraquand, J.; Kavraki, L.; Latombe, J.-C.; Motwani, R.; Li, T.-Y.; Raghavan, P., A random sampling scheme for path planning, International Journal of Robotics Research, 16, 6, 759-774 (1997) · doi:10.1177/027836499701600604 |
| [5] | Kuffner, J. J.; LaValle, S. M., RRT-Connect: An Efficient Approach to Single-Query Path Planning, Proceedings of the IEEE ICRA |
| [6] | Hsu, D.; Latombe, J.-C.; Kurniawati, H., On the probabilistic foundations of probabilistic roadmap planning, International Journal of Robotics Research, 25, 7, 627-643 (2006) · doi:10.1177/0278364906067174 |
| [7] | Karaman, S.; Frazzoli, E., Sampling-based algorithms for optimal motion planning, International Journal of Robotics Research, 30, 7, 846-894 (2011) · doi:10.1177/0278364911406761 |
| [8] | Marble, J. D.; Bekris, K. E., Asymptotically near-optimal planning with probabilistic roadmap spanners, IEEE Transactions on Robotics, 29, 2, 432-444 (2013) · doi:10.1109/TRO.2012.2234312 |
| [9] | Balkcom, D.; Kannan, A.; Lyu, Y.-H.; Wang, W.; Zhang, Y., Metric Cells: Towards Complete Search for Optimal Trajectories, Proceedings of the 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2015 |
| [10] | Elbanhawi, M.; Simic, M., Sampling-based robot motion planning: a review, IEEE Access, 2, 56-77 (2014) · doi:10.1109/ACCESS.2014.2302442 |
| [11] | Sun, Z.; Hsu, D.; Jiang, T.; Kurniawati, H.; Reif, J. H., Narrow passage sampling for probabilistic roadmap planning, IEEE Transactions on Robotics, 21, 6, 1105-1115 (2005) · doi:10.1109/TRO.2005.853485 |
| [12] | Boor, V.; Overmars, M. H.; van der Stappen, A. F., The Gaussian sampling strategy for probabilistic roadmap planners, Proceedings of the IEEE International Conference on Robotics and Automation |
| [13] | Wilmarth, S. A.; Amato, N. M.; Stiller, P. F., MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the space, Proceedings of the IEEE International Conference on Robotics and Automation |
| [14] | Siméon, T.; Laumond, J.-P.; Nissoux, C., Visibility-based probabilistic roadmaps for motion planning, Advanced Robotics, 14, 6, 477-493 (2000) · doi:10.1163/156855300741960 |
| [15] | Olfati-Saber, R.; Murray, R. M., Consensus problems in networks of agents with switching topology and time-delays, IEEE Transactions on Automatic Control, 49, 9, 1520-1533 (2004) · Zbl 1365.93301 · doi:10.1109/TAC.2004.834113 |
| [16] | Yan, J.; Yu, H., Distributed Optimization of Multiagent Systems in Directed Networks with Time-Varying Delay, Journal of Control Science and Engineering, 2017 (2017) · Zbl 1400.93018 · doi:10.1155/2017/7937916 |
| [17] | Weerakkody, S.; Liu, X.; Son, S. H.; Sinopoli, B., A graph-theoretic characterization of perfect attackability for secure design of distributed control systems, IEEE Transactions on Control of Network Systems, 4, 1, 60-70 (2017) · Zbl 1370.94620 · doi:10.1109/TCNS.2016.2573741 |
| [18] | Zhang, R.; Zhu, Q., Secure and resilient distributed machine learning under adversarial environments, Proceedings of the 18th International Conference on Information Fusion |
| [19] | Sundaram, S.; Gharesifard, B., Distributed Optimization Under Adversarial Nodes, IEEE Transactions on Automatic Control (2018) · Zbl 1482.90233 · doi:10.1109/TAC.2018.2836919 |
| [20] | Cortés, J.; Bullo, F., Coordination and geometric optimization via distributed dynamical systems, SIAM Journal on Control and Optimization, 44, 5, 1543-1574 (2005) · Zbl 1108.37058 · doi:10.1137/S0363012903428652 |
| [21] | Kwok, A.; Martinez, S., Unicycle coverage control via hybrid modeling, Institute of Electrical and Electronics Engineers Transactions on Automatic Control, 55, 2, 528-532 (2010) · Zbl 1368.93428 · doi:10.1109/TAC.2009.2037473 |
| [22] | Mahboubi, H.; Aghdam, A. G., Distributed deployment algorithms for coverage improvement in a network of wireless mobile sensors: relocation by virtual force, IEEE Transactions on Control of Network Systems, 4, 4, 736-748 (2017) · Zbl 1511.68036 · doi:10.1109/TCNS.2016.2547579 |
| [23] | Park, J.-H.; Bae, J.-H.; Baeg, M.-H., Adaptation algorithm of geometric graphs for robot motion planning in dynamic environments, Mathematical Problems in Engineering, 2016 (2016) |
| [24] | https://www.yaskawa.eu.com/en/products/robotic/motoman-robots/productdetail/product/mpx3500/ |
| [25] | Ferland, K., Discrete Mathematics (2008), Belmont, NY, USA: CENGAGE Learning, Belmont, NY, USA |
| [26] | Tao, T., An Introduction to Measure Theory (2011), American Mathematical Society · Zbl 1231.28001 · doi:10.1090/gsm/126 |
| [27] | Bertsekas, D. P., Constrained Optimization and Lagrange Multiplier Methods (1996), Massachusetts, MASS, USA: Athena Scientific, Massachusetts, MASS, USA |
| [28] | Bertsekas, D. P.; Tsitsiklis, J. N., Parallel and Distributed Computation: Numerical Methods (2014), Massachusetts, MASS, USA: Athena Scientific, Massachusetts, MASS, USA |
| [29] | Langbort, C.; Xiao, L.; D’Andrea, R.; Boyd, S., A decomposition approach to distributed analysis of networked systems, Proceedings of the 2004 43rd IEEE Conference on Decision and Control (CDC) |
| [30] | Tsitsiklis, J. N.; Bertsekas, D. P.; Athans, M., Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE Transactions on Automatic Control, 31, 9, 803-812 (1986) · Zbl 0602.90120 · doi:10.1109/tac.1986.1104412 |
| [31] | Sadegh, P., Constrained optimization via stochastic approximation with a simultaneous perturbation gradient approximation, Automatica, 33, 5, 889-892 (1997) · Zbl 0875.93573 · doi:10.1016/S0005-1098(96)00230-0 |
| [32] | Marti, K., Stochastic Optimization Methods (2008), Berlin Heidelberg: Springer, Berlin Heidelberg · Zbl 1194.74018 |
| [33] | Myers, R. H.; Montgomery, D. C.; Anderson-Cook, C. M., Response Surface Methodology: Process and Product in Optimization Using Designed Experiments (2009), John Wiley & Sons · Zbl 1269.62066 |
| [34] | Ebeida, M. S.; Mitchell, S. A.; Patney, A.; Davidson, A. A.; Owens, J. D., A simple algorithm for maximal poisson-disk sampling in high dimensions, Computer Graphics Forum, 31, 2, 785-794 (2012) · doi:10.1111/j.1467-8659.2012.03059.x |
| [35] | Jackson, E. A., Equilibrium Statistical Mechanics (1968), New Jersey, NJ, USA: Prentice-Hall, New Jersey, NJ, USA · Zbl 0167.56201 |
| [36] | Kocarev, L., Consensus and Synchronization in Complex Networks (2013), Berlin Heidelberg: Springer, Berlin Heidelberg |
| [37] | Barrat, A.; Barthélemy, M.; Vespignani, A., Dynamical Processes on Complex Networks (2008), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 1198.90005 · doi:10.1017/CBO9780511791383 |
| [38] | Ericson, C., Real-Time Collision Detection (2004), New York, NY, USA: CRC Press, New York, NY, USA · doi:10.1201/b14581 |
| [39] | Basener, W. F., Topology and Its Applications (2006), Hoboken, NJ, USA: John Wiley & Sons, Hoboken, NJ, USA · Zbl 1113.54001 · doi:10.1002/9780470067949 |
| [40] | Wang, X., Volumes of Generalized Unit Balls, Mathematics Magazine, 78, 5, 390-395 (2005) · Zbl 1085.51024 · doi:10.2307/30044198 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
