Decentralized On-Demand Resource Allocation for Autonomous Vehicle Fleets
Approche décentralisée pour l’allocation de courses à la demande à une flotte de véhicules autonomes
Institut Henri Fayol – Mines Saint-Etienne
Laboratoire Hubert Curien – University of Saint Etienne
Gauthier Picard email@example.com
Paolo Gianessi firstname.lastname@example.org
Flavien Balbo email@example.com
The development of autonomous vehicles, capable of communicating in a peer-to-peer manner, as well as the enthusiasm for
on-demand solutions (e.g. Uber, Lyft, Heetch), are the main motivation of this study. We are interested in setting up a fleet of autonomous electric taxis capable of responding in the absence of central control to requests for rides in an entire city, as to relieve communication infrastructure costs and improve reliability. Developing decentralized solutions, relying on vehicle-to-vehicle (V2V) interactions, with equivalent performances, could be a significant source of savings and resilience.
Modeling and developing decentralized systems is perfect fit for the Multi-Agent domain. Vehicle allocation problem is therefore a relevant application ground for such techniques.
We are interested here in solving allocation problems for autonomous vehicles (mostly electric) in a decentralized way. A fleet of autonomous vehicles is deployed to meet numerous requests from different locations of the city. Typically, this problem is solved centrally: requests are centralized in a portal where a fleet manager assigns requests to vehicles (ideally, optimally). This implies that the vehicles have continuous access to the portal (via a cellular network, for example). However, such access to such global switching infrastructure (for data collection and order submission) is costly and represents a critical bottleneck. The idea is to use inexpensive vehicle-to-vehicle (V2V) communication technologies to coordinate vehicles without global communication infrastructure.
We propose to model the various decision and optimization problems related to this more general problem. Indeed, several problems can appear according to the assumptions of work, as for example:
– do we know, even partially, the distribution of requests in space and time?
– can vehicles take more passengers or goods?
– are charging stations frequent?
Once these problems are modeled, the question of the choice and/or the design of centralized and decentralized solution methods arises. Methodologically, and considering the expertise of the Multi-Agent end Services project team, we want to explore the direction of distributed constraint optimization techniques (DCOP) and self-organized multi-agent techniques, compared to solutions from operational research.
The PhD candidate will work at Institut Henri Fayol, Mines Saint-Etienne, and Laboratoire Hubert Curien (https://laboratoirehubertcurien.univ-st-etienne.fr) in the Connected Intelligence team. This team has an expertise in multi-agent systems, distributed optimization and self-organization among others. This is a joint work with Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes (https://limos.isima.fr)
The three supervisors for this PhD thesis are:
• Gauthier Picard, Professor in Computer Science
• Paolo Gianessi, Associate Professor in Operation Research and Applied Mathematics
• Flavien Balbo, Professor in Computer Science
Funding the Ph.D. fellowship is funded for 3 years and is monthly funded about approximatively 1600€ net.
Profile of the candidate
The candidate should have a master degree or equivalent in computer science. The subject is at the intersection of several domains: AI, multi-agent systems, and operation research. Thus the candidate should have strong backgrounds in several of these topics.
Other required skills :
• Good abilities in algorithm design and programming
• a very good level (written and oral) in English
• good communication skills (oral and written)
• autonomy and motivation for research
Send your application with a CV, your last grade certificate (if you are currently finishing your Master’s degree, we need an official list of the grades you obtained so far in this degree with your rank among your peers), some recommendation letters and a specific motivation letter to firstname.lastname@example.org and email@example.com.
The application is opened until the 24th April. Some interviews will be offered between the 25th April and the 4th May.
The final decision will be given in June. The PhD thesis is expected to start in September (or October) 2018.
Egan, M., Jakob, M.: Market mechanism design for profitable on-demand transport services. Transportation Research Part B: Methodological 89, 178–195 (2016)
Ferdinando Fioretto, Enrico Pontelli and William Yeoh: Distributed Constraint Optimization Problems and Applications: A Survey, In Journal of Artificial Intelligence Resaerch 61, 623-698 (2018)
Grau, J.M.S., Romeu, M.A.E.: Agent based modelling for simulating taxi services. Procedia Computer Science 52, 902–907 (2015)
Maciejewski, M., Nagel, K.: The influence o fmulti-agent cooperation on the efficiency of taxi dispatching. In International Conference on Parallel Processing and Applied Mathematics. pp. 751–760. Springer (2013)
Santani, D., Balan, R.K., Woodard, C.J.: Spatio-temporal efficiency in a taxi dispatch system. In 6th International Conference on Mobile Systems, Applications, and Services, MobiSys (2008)
Shen, W., Lopes, C.: Managing autonomous mobility on demand systems for better passenger experience. In International Conference on Principles and Practice of Multi-Agent Systems. pp. 20–35. Springer (2015)
Gerardo Berbeglia, Jean-Francois Cordeau, and Gilbert Laporte. Dynamic pickup and delivery problems. European Journal of Operational Research, 202 (1):8–15. ISSN 03772217. doi:10.1016/j.ejor.2009.04.024 (2010)
Rinde R. S. van Lon and Tom Holvoet. When do agents outperform centralized algorithms? A systematic empirical evaluation in logistics. In CW Reports. Department of Computer Science, KU Leuven (2016).
Tamas Mahr, Jordan F. Srour, Mathijs de Weerdt, and Rob Zuidwijk. Can agents measure up? A comparative study of an agent-based and on-line optimization approach for a drayage problem with uncertainty. Transportation Research: Part C, 18(1):99–119. doi:10.1016/j.trc.2009.04.018. (2010)
Zargayouna, M., Balbo, F., Ndiaye, K.: Generic model for resource allocation in transporta- tion. application to urban parking management. Transportation Research Part C: Emerging Technologies 71, 538–554 (2016)
Professor, PhD, HDR
Laboratoire Hubert Curien UMR CNRS 5516
Institut Henri Fayol
MINES Saint-Étienne (EMSE)
158 cours Fauriel – 42023 Saint-Étienne Cedex 02 – FRANCE
room : EF 409
phone : +33 (0)4 77 42 66 84
Desinscription: envoyez un message a: firstname.lastname@example.org
Pour obtenir de l’aide, ecrivez a: email@example.com