I detta dokument studerar vi problemet med optimal multi-robot vägplanering (MPP) på grafer. Vi föreslår två multiflow baserade heltal linjär programmering (ILP) modeller som beräknar minsta sista ankomsttid och minsta totala avstånd lösningar för vår MPP formulering, respektive. De resulterande algoritmerna från dessa ILP-modeller är kompletta och garanterade att ge verkliga optimala lösningar. Dessutom kan vårt flexibla ramverk enkelt rymma andra varianter av MPP-problemet. Med fokus på den tidsoptimala algoritmen utvärderar vi dess prestanda, både som en fristående algoritm och som en generisk heuristisk för att snabbt lösa stora problemfall. Beräkningsresultat bekräftar effektiviteten i vår metod.
Jingjin och LaValle REF tar upp det optimala flerrobotsvägsplaneringsproblemet på grafen baserat på en minskning till linjära programmeringsproblem.
Planning optimal paths for multiple robots on graphs
{'venue': '2013 IEEE International Conference on Robotics and Automation', 'journal': '2013 IEEE International Conference on Robotics and Automation', 'mag_field_of_study': ['Engineering', 'Computer Science', 'Mathematics']}