Collision Avoidance System Synthesis for a Group of Robots in Unsupervised Learning Paradigm

Collision avoidance is very important problem in the domain of multi-robot interaction. In this paper we propose a new approach of collision avoidance in the context of the optimal control system synthesis problem definition with minimal information available. It is assumed that robots have a certain scope within which they can interact with static and dynamic phase constraints. A group of robots is considered to be homogeneous, and control system unit for reaching terminal states already available to robots. The control system which is responsible for collision avoidance is only activated when the nearest neighbor is located in the scope of the considered robot. The first important feature of this work is the fact that the collision avoidance between two robots is reciprocal with joint control system, without assigning priorities. Another key feature of this work is the complete absence of information about the environment and the current state of other robots at given time. Robots only share information with nearest neighbors if they locate in the scope of each other. We also present a computational experiment with mobile robots as control objects. A multilayer perceptron was used to approximate the control function. Weights of the perceptron were optimized in unsupervised paradigm by an algorithm belonging to the evolutionary strategies class. At the beginning of each epoch we generate a sample of collision scenarios for optimization, while the quality criterion of the achieved weights at the end of epoch is evaluated on a fixed test sample. Experimental results demonstrate strong ability of the optimized multilayer perceptron to map the relative state of two mobile robots to controls in order to avoid collisions.

1. LaValle S. M., Hutchinson S. A. Optimal Motion Planning for Multiple Robots Having Independent Goals, IEEETrans. on Robotics and Automation, 1998, vol. 14, no. 6, pp. 912—925.

2. Barraquand J., Latombe J. C. Robot motion planning: A distributed representation approach, The International Journal of Robotics Research, 1991, vol. 10, no. 6, pp. 628—649.

3. Barraquand J., Latombe J. C. Controllability of Mobile Robots with Kinematic Constraints, STANFORD UNIV CA DEPT OF COMPUTER SCIENCE, 1990, no. STAN-CS-90-1317.

4. Brooks R. A., Lozano-Perez T. A subdivision algorithm in configuration space for findpath with rotation, IEEE Transactions on Systems, Man, and Cybernetics, 1985, no. 2, pp. 224—233.

5. Faverjon B. Object level programming of industrial robots, Proceedings, 1986 IEEE International Conference on Robotics and Automation, IEEE, 1986, vol. 3, pp. 1406—1412.

6. Faverjon B., Tournassoud P. A local based approach for path planning of manipulators with a high number of degrees of freedom, Proceedings. 1987 IEEE International Conference on Robotics and Automation, IEEE, 1987, vol. 4, pp. 1152—1159.

7. Barraquand J., Langlois B., Latombe J. C. Robot motion planning with many degrees of freedom and dynamic constraints, The Fifth International Symposium On Robotics Research, 1991, pp. 435—444.

8. Zhu D., Latombe J. C. New heuristic algorithms for efficient hierarchical path planning, STANFORD UNIV CA DEPT OF COMPUTER SCIENCE, 1989, no. STAN-CS-89-1279.

9. Parsons D., Canny J. A motion planner for multiple mobile robots, Proceedings., IEEE International Conference on Robotics and Automation, IEEE, 1990, pp. 8—13.

10. LaValle S. M. Planning algorithms, Cambridge university press, 2006.

11. Sanchez G., Latombe J. C. Using a PRM planner to compare centralized and decoupled planning for multi-robot systems, Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No. 02CH37292), IEEE, 2002, vol. 2, pp. 2112—2119.

12. Oh J. H., Park J. H., Lim J. T. Centralized decoupled path planning algorithm for multiple robots using the temporary goal configurations //2011 Third International Conference on Computational Intelligence, Modelling and Simulation. IEEE, 2011, P. 206—209.

13. Van Den Berg J., Snoeyink J., Lin M. C., Manocha D. Centralized path planning for multiple robots: Optimal decoupling into sequential plans, Robotics: Science and Systems, 2009, vol. 2, no. 2(5), P. 2—3.

14. Devasia S., Iamratanakul D., Chatterji G., Meyer G. Decoupled conflict-resolution procedures for decentralized air traffic control, IEEE Transactions on intelligent transportation systems, 2011, vol. 12, no. 2, pp. 422—437.

15. Ermolov I.L, Iljuchin Ju.V, Sobolnikov S. A. Trajectory planning for autonomous mobile communicational robots, Vestnik MGTU Stankin, 2012, no. 4, pp. 96—100 (in Russian).

16. O’Donnell P. A., Lozano-Pérez T. Deadlock-free and collision-free coordination of two robot manipulators, ICRA, 1989, vol. 89, pp. 484—489.

17. Griswold N. C., Eem J. Control for mobile robots in the presence of moving objects, IEEE Transactions on Robotics and Automation, 1990, vol. 6, no. 2, pp. 263—268.

18. Pan T. J., Luo R. C. Motion planning for mobile robots in a dynamic environment with moving obstacles, Proceedings, IEEE International Conference on Robotics and Automation, IEEE, 1990, pp. 578—583.

19. Rude M. Collision avoidance by using space-time representations of motion processes, Autonomous Robots, 1997, vol. 4, no. 1, pp. 101—119.

20. Erdmann M., Lozano-Perez T. On multiple moving objects, Algorithmica, 1987, vol. 2, no. 1—4, pp. 477.

21. Bennewitz M., Burgard W., Thrun S. Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots, Robotics and autonomous systems, 2002, vol. 41, no. 2—3, pp. 89—99.

22. Clark C. M., Bretl T., Rock S. Applying kinodynamic randomized motion planning with a dynamic priority system to multi-robot space systems, Proceedings, IEEE Aerospace Conference, IEEE, 2002, vol. 7, pp. 7.

23. Grossman D. D. Traffic control of multiple robot vehicles, IEEE Journal on Robotics and Automation, 1988, vol. 4, no. 5, pp. 491—497.

24. Lumelsky V. J., Harinarayan K. R. Decentralized motion planning for multiple mobile robots: The cocktail party model, Autonomous Robots, 1997, vol. 4, no. 1, pp. 121—135.

25. Wang J., Beni G. Distributed computing problems in cellular robotic systems, EEE International Workshop on Intelligent Robots and Systems, Towards a New Frontier of Applications, IEEE, 1990, pp. 819—826.

26. Kato S., Nishiyama S., Takeno J. Coordinating mobile robots by applying traffic rules, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, 1992, vol. 3, pp. 1535—1541.

27. Koren Y., Borenstein J. Potential field methods and their inherent limitations for mobile robot navigation, ICRA, 1991, vol. 2, pp. 1398—1404.

28. Kapadia M., Singh S., Hewlett W., Reinman G., Faloutsos P. Parallelized egocentric fields for autonomous navigation, The Visual Computer, 2012, vol. 28, no. 12, pp. 1209—1227.

29. Wang L., Li Z., Wen C., He R., Guo F. Reciprocal Collision Avoidance for Nonholonomic Mobile Robots, 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), IEEE, 2018, pp. 371—376.

30. Huang X., Zhou L., Guan Z., Li Z., Wen C., He R. Generalized Reciprocal Collision Avoidance for Non-holonomic Robots, 2019 14th IEEE Conference on Industrial Electronics and Applications (ICIEA), IEEE, 2019, pp. 1623—1628.

31. Long P., Liu W., Pan J. Deep-learned collision avoidance policy for distributed multiagent navigation, IEEE Robotics and Automation Letters, 2017, vol. 2, no. 2, pp. 656—663.

32. Matarić M. J. Reinforcement learning in the multi-robot domain, Robot colonies, Springer, Boston, MA, 1997, pp. 73—83.

33. Stone P., Veloso M. Multiagent systems: A survey from a machine learning perspective, Autonomous Robots, 2000, vol. 8, no. 3, pp. 345—383.

34. Yang E., Gu D. Multiagent reinforcement learning for multi-robot systems: A survey. tech. rep, 2004.

35. Panait L., Luke S. Cooperative multi-agent learning: The state of the art, Autonomous agents and multi-agent systems, 2005, vol. 11, no. 3, pp. 387—434.

36. Godoy J. E., Karamouzas I., Guy S. J., Gini M. Adaptive learning for multi-agent navigation, Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 2015, pp. 1577—1585.

37. Kretzschmar H., Spies M., Sprunk C., Burgard W. Socially compliant mobile robot navigation via inverse reinforcement learning, The International Journal of Robotics Research, 2016, vol. 35, no. 11, pp. 1289—1307.

38. Dotsenko A., Diveev A., Cevallos J. P. C. Collision avoidance at swarm regrouping using modified network operator method with various number of arguments, 2019 14th IEEE Conference on Industrial Electronics and Applications (ICIEA), IEEE, 2019, pp. 768—773.

39. Glorot X., Bengio Y. Understanding the difficulty of training deep feedforward neural networks, Proceedings of the thirteenth international conference on artificial intelligence and statistics, 2010, pp. 249—256.

40. Salimans T., Ho J., Chen X., Sidor S., Sutskever I. Evolution strategies as a scalable alternative to reinforcement learning, arXiv preprint arXiv:1703.03864, 2017.

41. Brockhoff D., Auger A., Hansen N., Arnold D. V., Hohm T. Mirrored sampling and sequential selection for evolution strategies, International Conference on Parallel Problem Solving from Nature, Springer, Berlin, Heidelberg, 2010, pp. 11—21.

42. Wierstra D., Schaul T., Glasmachers T., Sun Y., Peters J., Schmidhuber J. Natural evolution strategies, The Journal of Machine Learning Research, 2014, vol. 15, no. 1, pp. 949—980.