Towards Optimal Solution of Robotic Routing Problems
Project goals
In the project, we aim to establish theoretical foundations for solving robotic routing problems with continuous optimization. We plan to leverage existing theoretical results on lower bound estimations of the close enough traveling salesman problem and model-based multi-goal motion planning for the Dubins vehicle model towards a general solution to combinatorial routing with continuous optimization problems arising in robotic scenarios. We target to establish algorithmic foundations for solution quality estimations based on tight lower bounds that can be employed in efficient pruning of search space and thus support finding optimal solutions. We target to 1) optimal solutions of routing problems with cost corresponding to the continuous optimization of multivariable functions arising from limitations of robotic systems; 2) design new efficient algorithms with machine learning-enabled scalability to solve large practical instances of realistic problems; 3) establish complex analysis and empirical evaluation of the developed solutions in experimental scenarios with robotic systems.
Keywords
robotic information gatheringmotion planningrobotic traveling salesman problem
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202200004
Main participants
České vysoké učení technické v Praze / Fakulta elektrotechnická
Contest type
VS - Public tender
Contract ID
22-05762S
Alternative language
Project name in Czech
Optimální řešení robotických směrovacích úloh
Annotation in Czech
Navrhovaný projekt si klade za cíl vytvořit teoretické základy optimálního řešení robotických směrovacích úloh. V projektu plánujeme zobecnit existující výsledky řešení robotických úloh obchodního cestujícího s okolím a plánování založené na modelu pohybu Dubinsova vozidla. Naším cílem je vytvořit algoritmické základy odhadu kvality řešení založené na těsných dolních mezích, které lze využít k efektivnímu prořezání prohledávaného prostoru možných sekvencí a tím podpořit nalezení optimálního nebo optimu blízkého řešení. V projektu se zaměřujeme na 1) optimální řešení směrovacích úloh s cenou pohybu odpovídající spojité optimalizaci funkcí více proměnných vyplývající z omezení robotických systémů; 2) návrhu efektivních algoritmů založených na strojovém učení umožňující praktické řešení realistických instancí plánovacích úloh; 3) stanovení vlastností vyvinutých algoritmů a jejich validaci v experimentálních scénářích se skutečnými robotickými systémy.
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
20204 - Robotics and automatic control
OECD FORD - another secondary branch
20205 - Automation and control systems
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
JD - Use of computers, robotics and its application
Solution timeline
Realization period - beginning
Jan 1, 2022
Realization period - end
Dec 31, 2024
Project status
—
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
Mar 12, 2025
Finance
Total approved costs
6,707 thou. CZK
Public financial support
6,464 thou. CZK
Other public sources
243 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
6 707 CZK thou.
Public support
6 464 CZK thou.
96%
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. 2022 - 31. 12. 2024