Doctorat : représentation de terrains dynamiques à l'aide de graphes et l'application à la planification et à la coordination d'agents autonomes dans le domaine agricole

Retour à la liste des résultats

Présentation INRAE

L’Institut national de recherche pour l’agriculture, l’alimentation et l’environnement (INRAE) est un établissement public de recherche rassemblant une communauté de travail de 12 000 personnes, avec 272 unités de recherche, de service et expérimentales, implantées dans 18 centres sur toute la France. INRAE se positionne parmi les tout premiers leaders mondiaux en sciences agricoles et alimentaires, en sciences du végétal et de l’animal. Ses recherches visent à construire des solutions pour des agricultures multi-performantes, une alimentation de qualité et une gestion durable des ressources et des écosystèmes.

Environnement de travail, missions et activités

La modélisation par agents autonomes peut aider à la planification de tâches agricoles [DFV21, SBGV18] : travaux sur les parcelles, observation ou transport de matériel. De nombreuses recherches ont été menées sur la planification et le cheminement d’agents autonomes, mais principalement dans des environnements contrôlés : logistique ou industrie. L’adaptation au contexte agricole de ces questions ouvre de nouveaux défis, notamment la prise en compte de :

- la dynamicité du terrain et les conditions météorologiques impactant les possibilités de perception et de déplacement des agents ;

- l’hétérogénéité des agents, que ce soit en termes de taille et de mode de déplacement (différents modes terrestres, mais aussi aériens), ainsi que la gestion de leur autonomie (moindre densité de stations de recharge).

La thèse poursuivra plusieurs objectifs. Tout d’abord, il faudra proposer un modèle permettant de représenter le terrain en prenant en compte son aspect dynamique. On utilisera notamment les graphes temporels et dynamiques, qui sont un sujet en pleine expansion [M16, O22], notamment vis-à-vis des questions de chemins [CHMZ21, CDFK24, MS16]. Par la suite, il faudra développer des algorithmes de planification et de cheminement permettant aux agents d’effectuer leurs tâches en minimisant le risque d’incident tout en étant efficace. On pourra adopter des modèles centraux ou plus distribués selon le problème, mais une composante online sera essentielle pour faire face à des imprévus et actualiser les informations des agents. Des inspirations possibles sont le Voyageur Canadien [ASA16], le Multi-Agent Path Finding [DBJP21, SSF+19] ou des approches hybrides mêlant méthodes exactes et heuristiques [AMJP09, CMBM24]. Enfin, le modèle et les algorithmes seront mis à l’épreuve à l’aide de simulations, voire d’expérimentations de terrain.

Il sera attendu de produire des résultats à la fois fondamentaux (complexité, garanties de performance, de complétude et/ou de qualité des algorithmes) et appliqués (expérimentations). L’équilibre exact entre ces deux aspects dépendra du candidat ou de la candidate retenu⋅e, mais les deux devront être abordés.

La thèse s’effectuera au sein de l’unité TSCF (Technologies et Systèmes d’Information pour les Agrosystèmes), située sur le campus des Cézeaux de Clermont-Ferrand. Il sera aussi possible de se rendre sur le site expérimental de Montoldre, dans l’Allier, pour y effectuer des expérimentations (représentation du terrain, test des algorithmes en conditions réelles).

La thèse sera également coencadrée par le LIG à Grenoble, plusieurs allers-retours seront prévus (et financés) chaque année.

Les travaux seront publiés dans des conférences et journaux internationaux à comité de lecture en algorithmique ou en intelligence artificielle, mais aussi présentés dans des workshops, séminaires et journées scientifiques, y compris de projets portés au sein de l’unité et liés aux thématiques de la thèse (Ninsar, OCOD...).

[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.

Formations et compétences recherchées

Formation recommandée : Master en informatique avec une coloration algorithmique (théorique ou appliquée)

Connaissances souhaitées : Théorie des graphes, développement d’algorithmes et leur implémentation (C++, Rust et/ou Python), théorie de la complexité

Expérience appréciée : Stage de recherche

Aptitudes recherchées : Compétences en recherche fondamentale, curiosité scientifique, rédaction et communication scientifique, autonomie et initiative, travail en équipe

Votre qualité de vie à INRAE

En rejoignant INRAE, vous bénéficiez (selon le type de contrat et sa durée) :

-  jusqu'à 30 jours de congés + 15 RTT par an (pour un temps plein) ;
- d'un soutien à la parentalité : CESU garde d'enfants, prestations pour les loisirs ;
- de dispositifs de développement des compétences : formation, conseil en orientation professionnelle ;
- d'un accompagnement social : conseil et écoute, aides et prêts sociaux ;
- de prestations vacances et loisirs : chèque-vacances, hébergements à tarif préférentiel ;
- d'activités sportives et culturelles ;
- d'une restauration collective.

Le site des Cézeaux est desservi par la ligne de Tram A, il est également équipé de stationnements et de services dédiés à la pratique du vélo.

 

Modalités pour postuler

J'envoie mon CV et ma lettre de motivation