Hybrid Algorithm of Situational Trajectory Planning under Partial Uncertainty

The paper describes a hybrid algorithm of situational trajectory planning under partial uncertainty for the two-dimensional space. The algorithm is based on integration of the wave algorithm and ant colony optimization and makes it possible to build a real-time trajectory of minimal length with simultaneous optimization of a number of other constructed path quality criteria. The trajectory laying process is carried out step by step. The constraints on the area map which make it impossible to lay the trajectory from the current position are identified after the trajectory reaching this position. Successively at each step relatively to the current position of a mobile object (MO), a zone is formed within which, by means of radar, all obstacles are localized, and then a trajectory section is built being a continuation of the previously obtained section. The whole trajectory is a set of sections linking the original position of the mobile object to the target position. The time complexity of the hybrid algorithm depends on the lifetime of colonies l (number of iterations), the number n of the graph vertices and the number of ants m, and is defined as O (ln²m)

References

[1] Pshikhopov V.Kh., ed. Intellektualnoe planirovanie traektoriy podvizhnykh obektov v sredakh s prepyatstviyami [Intelligent planning of moving objects trajectory in environment with obstacles]. Moscow, Fizmatlit Publ., 2014. 295 p.

[2] Pshikhopov V.Kh., Medvedev M.Yu. Upravlenie podvizhnymi ob"ektami v opredelennykh i neopredelennykh sredakh [Control on moving objects in certain and uncertain environment]. Moscow, Nauka Publ., 2011. 215 p.

[3] Guzik V.F., Pereverzev V.A., Pyavchenko A.O., Saprykin R.V. Design principles for extrapolating multidimensional neural-network planner for intellectual position-trajectory control system of moving objects. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, no. 2 (175), pp. 67–80 (in Russ.).

[4] Gorbatov V.A. Osnovy diskretnoy matematiki [Fundamentals of discrete mathematics]. Moscow, URSS Publ., 1994. 340 p.

[5] Aho A., Ullman J., Hopcroft J. The design and analysis of computer algorithms. Addison-Wesley, 1974. 70 p.

[6] Pshikhopov V.Kh., Medvedev M.Yu., Gurenko B.V. The basic algorithms of adaptive position-trajectory control system of mobile objects. Problemy upravleniya [Control Sciences], 2015, no. 4. pp. 66–74 (in Russ.).

[7] McConnell J.J. Analysis of algorithms. Jones & Bartlett Learning, 2001. 297 p.

[8] Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy [Modern search optimization algorithms. Algorithms inspired by nature]. Moscow, Bauman MSTU Publ., 2014. 446 p.

[9] Caro G.Di, Ducatelle F., Gambardella L.M. AntHocNet: An adaptive nature inspired algorithm for routing in mobile ad hoc networks. Transactions on Emerging Telecommunications Technologies, 2005, vol. 16, iss. 5, pp. 443–455. DOI: 10.1002/ett.1062

[10] Hoefler T., Snir M. Generic topology mapping strategies for large-scale parallel architectures. ICS11. Proc. of the Int. Conf. on Supercomputing, ACM, 2011, pp. 75–85.

[11] Neydorf R.A., Polyakh V.V., Chernogorov I.V., Yarakhmedov O.T. Study of heuristic algorithms in planning and optimization of routes problem in the environment with obstacles. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, no. 3 (176). pp. 127–143 (in Russ.).

[12] Fatemeh K.P., Fardad F., Reza S.N. Comparing the performance of genetic algorithm and ant colony optimization algorithm for mobile robot path planning in the dynamic environments with different complexities. Journal of Academic and Applied Studies, 2013, vol. 3, no. 2, pp. 29–44.

[13] Dutta S. Obstacle avoidance of mobile robot using PSO-based neuro fuzzy technique. International Journal on Computer Science and Engineering, 2010, vol. 2, no. 2, pp. 301–304.

[14] Chen S., Eshaghian M.M. A fast recursive mapping algorithm. Department of computer and information science. New Jersey Institute of Technology, 2013, pp. 219–227.

[15] Raidl G.R. A unified view on hybrid metaheuristics. International Workshop on Hybrid Metaheuristics, Springer, 2006, pp. 1–12.

[16] Dorigo M., Caro G.Di, Gambardella L.M. Ant algorithms for discrete optimization. Artificial Life, 1999, vol. 5, no. 2, pp. 137–172.

[17] Lebedev O.B. Modeli adaptivnogo povedeniya muravinoy kolonii v zadachakh proektirovaniya [Adaptive behavior model for ant colony in design problems]. Taganrog, YuFU Publ., 2013. 199 p.

[18] Lebedev B.K., Lebedev O.B. Modelling of an ant colony adaptive behavior by search of the decisions interpreted by trees. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, no. 7, pp. 27–34 (in Russ.).