Jak znaleźć najkrótszą ścieżkę w dynamicznej sytuacji

Question

Kilka dni temu, Ktoś zapytał mnie, czy w naszym środowisku znajdują się agenci i chcą przejść ze swoich źródeł do miejsc docelowych, w jaki sposób możemy znaleźć najkrótszą ścieżkę dla wszystkich takie, że nie powinny mieć konfliktu podczas spaceru.

Problem polega na tym, że wszyscy agenci jednocześnie chodzą w środowisku (co może być modelowane przez nieukierunkowany wykres ważony) i nie powinniśmy mieć kolizji. Myślałem o tym, ale nie mogłem znaleźć optymalnej ścieżki dla nich wszystkich. Ale na pewno jest zbyt wiele heurystycznych pomysłów na ten problem.

Załóżmy wejście jest wykresem G (V, E), środki m, które są w: s , S , ..., S _m węzły wykresie na starcie i powinien przejść do węzłów D , ... D _m na końcu. Również może być tam jest konflikt w węzłach S _i lub D _i ... ale konflikty te nie są ważne, nie powinny one mieć konflikt, gdy są one w ich wewnętrznych węzłów swojej drodze.

Jeśli ich ścieżka nie powinna mieć tego samego węzła wewnętrznego, będzie to pewnego rodzaju problem z k-disjoint paths, który jest NPC, ale w tym przypadku ścieżki mogą mieć te same węzły, ale agent nie powinien znajdować się w tym samym węźle w tym samym czasie. Nie wiem, czy mogę podać dokładny opis problemu, czy nie. Jeśli jest mylące, powiedz mi w komentarzach, aby go edytować.

Czy istnieje optymalny i szybki algorytm (optymalnie, mam na myśli, że suma długości wszystkich ścieżek jest możliwie najmniejsza, a przez szybki mam na myśli dobry algorytm wielomianowy).

Answer 1

Google ujawnia dwa linki, które mogą być pomocne:

• Cooperative path planning for multi-robot systems in dynamic domains
• Optimizing schedules for prioritized path planning of multi-robot systems

EDIT: z rozdziału książki (pierwszy link):

Istnieje wiele podejść do planu ścieżki w systemie z wieloma robotami [sic], jednak znalezienie optymalnego rozwiązania o wartości jest NP-trudne. Hopcraft i in. (1984) upraszczają problem z planowaniem do problemu przenoszenia prostokątów w prostokątnym pojemniku. Udowodnili twardość NP znajdującą plan z danej konfiguracji do konfiguracji celu z najmniejszą liczbą kroków . W związku z tym wszelkie możliwe podejścia do planowania ścieżek są kompromisem między wydajnością a dokładnością wyniku.

nie mogę znaleźć oryginalnego papieru przez Hopcroft on-line, ale biorąc pod uwagę, że cytat, podejrzewam problem one zredukowane zadania nawigacyjnego jest podobna do Rush Hour, który jest PSPACE-zupełny.

Answer 2

Jeśli jest to tylko kwestia dotarcia z punktu A do punktu B dla każdego robota, można po prostu użyć algorytmu wyszukiwarki jak A* (A Star) lub Best-First.

Daj mu prostą heurystykę, taką jak suma odległości od celu.

wyszukiwania