An autonomous vehicle sequencing problem at intersections: A genetic algorithm approach

Yan, F. ; Dridi, M. ; El Moudni, A.

International Journal of Applied Mathematics and Computer Science, Tome 23 (2013) no. 1, pp. 183-200.

Résumé

This paper addresses a vehicle sequencing problem for adjacent intersections under the framework of Autonomous Intersection Management (AIM). In the context of AIM, autonomous vehicles are considered to be independent individuals and the traffic control aims at deciding on an efficient vehicle passing sequence. Since there are considerable vehicle passing combinations, how to find an efficient vehicle passing sequence in a short time becomes a big challenge, especially for more than one intersection. In this paper, we present a technique for combining certain vehicles into some basic groups with reference to some properties discussed in our earlier works. A genetic algorithm based on these basic groups is designed to find an optimal or a near-optimal vehicle passing sequence for each intersection. Computational experiments verify that the proposed genetic algorithms can response quickly for several intersections. Simulations with continuous vehicles are carried out with application of the proposed algorithm or existing traffic control methods. The results show that the traffic condition can be significantly improved by our algorithm.

Détail

Keywords: autonomous vehicle, autonomous intersection management, genetic algorithm, dynamic programming, heuristics
Mots-clés : pojazd autonomiczny, algorytm genetyczny, programowanie dynamiczne

Bibliographie

[1] Akpinar, S. and Bayhan, G.M. (2010). A hybrid genetic algorithm for mixed model assembly line balancing problem with parallel workstations and zoning constraints, Engineering Applications of Artificial Intelligence 24(3): 449–457.

[2] Aotani, T., Yamaoka, S. and Tajima, T. (2002). Research development of driving safety support systems, Proceedings of the 41st SICE Annual Conference, Osaka, Japan, Vol. 3, pp. 1792–1797.

[3] Aytug, H., Khouja, M. and Vergara, F.E. (2003). Use of genetic algorithms to solve production and operations management problems: A review, International Journal of Production Research 41(17): 3995–4009.

[4] Belter, D. and Skrzypczyński, P. (2010). A biologically inspired approach to feasible gait learning for a hexapod robot, International Journal of Applied Mathematics and Computer Science 20(1): 69–84, DOI: 10.2478/v10006-010-0005-7.

[5] Bertolazzi, E., Biral, F., Da Lio, M., Saroldi, A. and Tango, F. (2010). Supporting drivers in keeping safe speed and safe distance: The SASPENCE subproject within the European Framework Programme 6 Integrating Project Prevent, IEEE Transactions on Intelligent Transportation Systems 11(3): 525–538.

[6] Chisalita, L. and Shahmehri, N. (2002). A peer-to-peer approach to vehicular communication for the support of traffic safety applications, Proceedings of the IEEE 5th International Conference on Intelligent Transportation Systems, Singapore, pp. 336–341.

[7] Dresner, K. and Stone, P. (2004). Multiagent traffic management: A reservation-based intersection control mechanism, Proceedings of Autonomous Agents and Multiagent Systems AAMAS’04, New York, NY, USA, pp. 530–537.

[8] Dresner, K. and Stone, P. (2006). Traffic intersections of the future, Proceedings of the 21st National Conference on Artificial Intelligence, Boston, MA, USA, pp. 1593–1596.

[9] Dridi, M. and Kacem, I. (2004). A hybrid approach for scheduling transportation networks, International Journal of Applied Mathematics and Computer Science 14(3): 397–409.

[10] Fang, F. and Elefteriadou, L. (2006). Development of an optimization methodology for adaptive traffic signal control at diamond interchanges, Journal of Transportation Engineering 132(8): 629–637.

[11] Gradinescu, V., Gorgorin, C., Diaconescu, R., Cristea, V. and Iftode, L. (2007). Adaptive traffic lights using car-to-car communication, Proceedings of the IEEE 65th Vehicular Technology Conference, VTC2007-Spring, Dublin, Ireland, pp. 21–25.

[12] Hall, R. W. and Papageorgiou, M. (1999). Handbook of Transportation Science, Springer, New York, NY/Boston, MA/Dordrecht/London/Moscow.

[13] Hart, E., Ross, P. and Corne, D. (2005). Evolutionary scheduling: A review, Genetic Programming and Evolvable Machines 6(2): 191–220.

[14] Huang, Q. and Miller, R. (2003). The design of reliable protocols for wireless traffic signal systems, Technical report, Department of Computer Science and Engineering, Washington University, Saint Louis, MO.

[15] Hunt, P. (1982). The scoot on-line traffic signal optimization technique, Traffic Engineering Control 23(4): 190–192.

[16] Kashan, A., Karimi, B. and Jenabi, M. (2008). A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes, Computers Operations Research 35(4): 1084–1098.

[17] Kato, S., Tsugawa, S., Tokuda, K., Matsui, T. and Fujii, H. (2002). Vehicle control algorithms for cooperative driving with automated vehicles and intervehicle communications, IEEE Transactions of Intelligent Transportation Systems 3(3): 155–161.

[18] Lachner, R. (1997). Collision avoidance as a differential game: real-time approximation of optimal strategies using higher derivatives of the value function, Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Orlando, FL, USA, Vol. 3, pp. 2308–2313.

[19] Li, L. and Wang, F. (2006). Cooperative driving at blind crossings using intervehicle communication, IEEE Transactions on Vehicular Technology 55(6): 1712–1724.

[20] Nadeem, T., Dashtinezhad, S. and Liao, C. (2004). TrafficView: A scalable traffic monitoring system, Proceedings of the IEEE International Conference on Mobile Data Management, Berkeley, CA, USA, pp. 13–26.

[21] Robertson, D. (1969). TRANSYT: A traffic network study tool, Technical Report TRRL-LR-253, Transport and Road Research Laboratory, Crowthorne.

[22] Shladover, S., Desoer, C., Hedrick, J., Tomizuka, M., Walrand, J., Zhang, W.-B., McMahon, D., Peng, H., Sheikholeslam, S. and McKeown, N. (1991). Automated vehicle control developments in the path program, IEEE Transactions on Vehicular Technology 40(1): 114–130.

[23] Shladover, S.E. (2007). Path at 20—History and major milestones, IEEE Transactions on Intelligent Transportation Systems 8(4): 1 22–1 29.

[24] Wang, D., Gen, M. and Cheng, R. (1999). Scheduling grouped jobs on single machine with genetic algorithm, Computers Industrial Engineering 36(2): 309–324.

[25] Webster, F. (1958). Road research technical paper, Technical report, Road Research Laboratory, London.

[26] Witkowska, A., Tomera, M. and Śmierzchalski, R. (2007). A backstepping approach to ship course control, International Journal of Applied Mathematics and Computer Science 17(1): 73–85, DOI: 10.2478/v10006-007-0007-2.

[27] Wu, J., Abbas-Turki, A. and El Moudni, A. (2009). Discrete methods for urban intersection traffic controlling, Proceedings of the IEEE 69th Vehicular Technology Conference, Barcelona, Spain, pp. 1–5.

[28] Xing, L., Chen, Y., Yang, K., Hou, F., Shen, X. and Cai, H.-P. (2008). A hybrid approach combining an improved genetic algorithm and optimization strategies for the asymmetric traveling salesman problem, Engineering Applications of Artificial Intelligence 21(8): 1370–1380.

[29] Yan, F., Dridi, M. and El-Moudni, A. (2009). A branch and bound algorithm for new traffic signal control system of an isolated intersection, 39th International Conference on Computers Industrial Engineering, CIE39, Troyes, France, pp. 999–1004.

[30] Yan, F., Dridi, M. and El-Moudni, A. (2012). New vehicle sequencing algorithms with vehicular infrastructure integration for an isolated intersection, Telecommunication Systems 50(4): 325–337.