A common problem in the field of robotics is to coordinate motions of multiple robots to ensure the shortest possible execution time. The problem is known PSPACE-complete, thus, it is impossible to find the best solution in a reasonable time for large scale problems. For this reason, in this work we look for sub-optimal solutions by systematically improving a given one. We present a heuristic algorithm to reduce execution time of a path by changing robots' priorities in case of path overlap. The algorithm is applied to a solution computed by a decoupled method in a discrete event system context. It is shown that the proposed approach is effective in finding a solution with shorter execution time. Tests show that the proposed algorithm can achieve improvement up to 45%.
A heuristic algorithm to optimize execution time of multi-robot path
DEPLANO, DIEGO
Primo
;Giua, AlessandroUltimo
2017-01-01
Abstract
A common problem in the field of robotics is to coordinate motions of multiple robots to ensure the shortest possible execution time. The problem is known PSPACE-complete, thus, it is impossible to find the best solution in a reasonable time for large scale problems. For this reason, in this work we look for sub-optimal solutions by systematically improving a given one. We present a heuristic algorithm to reduce execution time of a path by changing robots' priorities in case of path overlap. The algorithm is applied to a solution computed by a decoupled method in a discrete event system context. It is shown that the proposed approach is effective in finding a solution with shorter execution time. Tests show that the proposed algorithm can achieve improvement up to 45%.File | Dimensione | Formato | |
---|---|---|---|
17icca.pdf
Solo gestori archivio
Tipologia:
versione editoriale
Dimensione
202.04 kB
Formato
Adobe PDF
|
202.04 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.