Multi-Robotic Path Planning and Execution
Project goals
Multi-agent pathfinding (MAPF) is an abstract model for planning the collision-free movement of a group of agents in a shared environment. When applying MAPF techniques to actual robots, for example, in autonomous warehouses, the planning techniques need to fulfill several criteria that the current academic MAPF research does not adequately address. They need to scale to many robots, provide flexibility during plan execution to accommodate minor deviations from the plans, detect possible future issues (collisions) caused by inaccuracies in plan execution or environment changes, and respond adequately to these dynamic changes. We first compare the scalability and solution quality of AI and robotics approaches to solving the MAPF problem. We propose novel planning techniques appropriate for real robots, focusing on the robustness and flexibility of plans. We suggest how to diagnose future failures (collisions) during execution and resolve these failures before they happen.
Keywords
path planningplan executiondiagnosticsre-planningmulti-robotic systems
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202300001
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
23-05104S
Alternative language
Project name in Czech
Multi-robotické plánování cest a jejich exekuce
Annotation in Czech
Multi-agentní hledání cest (Multi-agent pathfinding, MAPF) je abstraktní model problému hledání nekolizních cest pro skupinu agentů pohybujících se ve sdíleném prostředí. Při aplikaci technik MAPF na skutečných robotech, například v autonomních skladech, musí plánovací techniky splňovat specifická kritéria, která dosavadní akademický výzkum plně neodráží. Algoritmy by měly být schopné pracovat s velkým množstvím robotů, vytvářet flexibilní plány vyvažující drobné nepřesnosti při provádění plánů, detektovat možné budoucí kolize způsobené nepřesností při provádění plánů či vnějšími vlivy a adekvátně na tyto dynamické změny reagovat. V projektu nejprve porovnáváme přístupy k řešení MAPF problému navržené v robotické a AI komunitě a to z pohledu škálovatelnosti a kvality řešení. Dále navrhneme nové techniky pro plánování cest robotů s důrazem na robustnost a flexibilitu plánů. Nakonec vytvoříme diagnostické přístupy pro detekování budoucích problémů (kolizí) při provádění plánů a navrhneme, jak tyto problémy řešit dříve, než nastanou.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Solution timeline
Realization period - beginning
Jan 1, 2023
Realization period - end
Dec 31, 2025
Project status
K - Ending multi-year project
Latest support payment
Feb 29, 2024
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP25-GA0-GA-R
Data delivery date
Feb 21, 2025
Finance
Total approved costs
8,775 thou. CZK
Public financial support
7,752 thou. CZK
Other public sources
1,023 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
8 775 CZK thou.
Public support
7 752 CZK thou.
88%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 01. 2023 - 31. 12. 2025