PhD Thesis on the representation of dynamic terrain with graphs and application to planning and coordination of autonomous agents in an agricultural setting

Back to jobs listing

INRAE presentation

The French National Research Institute for Agriculture, Food, and Environment (INRAE) is a major player in research and innovation. It is a community of 12,000 people with 272 research, experimental research, and support units located in 18 regional centres throughout France. Internationally, INRAE is among the top research organisations in the agricultural and food sciences, plant and animal sciences, as well as in ecology and environmental science. It is the world’s leading research organisation specialising in agriculture, food and the environment. INRAE’s goal is to be a key player in the transitions necessary to address major global challenges. Faced with a growing world population, climate change, resource scarcity, and declining biodiversity, the Institute has a major role to play in building solutions and supporting the necessary acceleration of agricultural, food and environmental transitions.

Work environment, missions and activities

Using autonomous agents can help planning agricultural tasks [DFV21, SBGV18]: work on the farms, observation, tool transportation. Most of the research on path planning and path finding for autonomous agents has been made in controlled environments, such as logistics or industry. Working in the agricultural setting opens new challenges, such as:

- terrain dynamicity and weather conditions which impact agents’ perception and movement;

- the diversity of agents, be it in terms of size and movement (different terrestrial movement, aerial drones), and the management of their energy consumption (lesser density for charging docks).

The thesis will pursue several goals. The first one is to develop a model for representing agricultural terrain, taking its dynamicity into account. We will use temporal and dynamic graphs [M16, O22], models on which path problems have recently been studied [CHMZ21, CDFK24, MS16]. The second goal is to conceive algorithms for path planning and path finding, allowing the agents to accomplish their tasks with high efficiency and low risks. Both centralized and distributed models can be considered, but an online component will be necessary to adapt to the uncertain nature of the environment. Possible ideas to consider are the Canadian Traveler Problem [ASA16], Multi-Agent Path Finding [DBJP21, SSF+19] or mixing exact methods and heuristics [AMJP09 , CMBM24]. Finally, the model and the algorithms will be tested through simulations and practical experimentations.

The thesis will produce results of both theoretical (complexity, performance guarantees, completeness of algorithms) and applied (experimentation) nature. The exact balance between those two aspects will depend on the hired candidate’s skills and motivation, but both will have to be considered.

[AMJP09] Ahmadzadeh, A., Motee, N., Jadbabaie, A., & Pappas, G. (2009, May). Multi-vehicle path planning in dynamically changing environments. In 2009 IEEE international conference on Robotics and Automation (pp. 2449-2454). IEEE.

[ASA16] Aksakalli, V., Sahin, O. F., & Ari, I. (2016). An AO* based exact algorithm for the Canadian traveler problem. INFORMS Journal on Computing, 28(1), 96-111.

[CMBM24] Cariou, C., Moiroux-Arvis, L., Bendali, F., & Mailfert, J. (2024, May). Optimal route planning of an Unmanned Aerial Vehicle for data collection of agricultural sensors. In IEEE INFOCOM 2024-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) (pp. 1-6). IEEE.

[CHMZ21] Casteigts, A., Himmel, A. S., Molter, H., & Zschoche, P. (2021). Finding temporal paths under waiting time constraints. Algorithmica, 83(9), 2754-2802.

[CDFK24] Chakraborty, D., Dailly, A., Foucaud, F., & Klasing, R. (2024). Algorithms and complexity for path covers of temporal DAGs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) . Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[DBJP21] Das, P. K., Behera, H. S., Jena, P. K., & Panigrahi, B. K. (2021). An intelligent multi-robot path planning in a dynamic environment using improved gravitational search algorithm. International Journal of Automation and Computing, 18, 1032-1044.

[DFV21] Davoodi, M., Faryadi, S., & Velni, J. M. (2021). A graph theoretic-based approach for deploying heterogeneous multi-agent systems with application in precision agriculture. Journal of Intelligent & Robotic Systems, 101, 1-15.

[LSF+19] Li, J., Surynek, P., Felner, A., Ma, H., Kumar, T. S., & Koenig, S. (2019, July). Multi-agent path finding for large agents. In Proceedings of the AAAI Conference on Artificial Intelligence 33(01), 7627-7634.

[M16] Michail, O. (2016). An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4), 239-280.

[MS16] Michail, O., & Spirakis, P. G. (2016). Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634, 1-23.

[O22] Oettershagen, L. (2022). Temporal graph algorithms (Doctoral dissertation, Universitäts-und Landesbibliothek Bonn).

[SBGV18] Skobelev, P., Budaev, D., Gusev, N., & Voschuk, G. (2018). Designing multi-agent swarm of uav for precise agriculture. In Highlights of Practical Applications of Agents, Multi-Agent Systems, and Complexity: The PAAMS Collection: International Workshops of PAAMS 2018, Toledo, Spain, June 20–22, 2018, Proceedings 16 (pp. 47-59). Springer International Publishing.

[SSF+19] Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T., ... & Boyarski, E. (2019). Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of the International Symposium on Combinatorial Search 10(1), 151-158.

Training and skills

Recommended training: Masters degree in Computer Science or Mathematics with an algorithms focus

Desired knowledge: Graph Theory, Algorithms, Development (C++, Rust and/or Python), Complexity Theory

Appreciated experience: Research internships or jobs

Skills: Fundamental research, scientific curiosity, scientific writing and communication, autonomy  and initiative, teamwork

INRAE's life quality

By joining our teams, you benefit from (depending on the type of contract and its duration):

- up to 30 days of annual leave + 15 days "Reduction of Working Time" (for a full time);
- parenting support: CESU childcare, leisure services;
- skills development systems: training, career advise;
- social support: advice and listening, social assistance and loans;
- holiday and leisure services: holiday vouchers, accommodation at preferential rates;
- sports and cultural activities;
- collective catering.

Les Cézeaux site is served by tramway A, and is also equipped with parking facilities and services dedicated to cycling.

How to apply

I send my CV and my motivation letter