Wie kann vermieden werden, dass der Roboter im lokalen Minimum gefangen wird?

Question

Ich beschäftige mich schon seit einiger Zeit mit der Bewegungsplanung für Roboter und habe seit einiger Zeit die Möglichkeit untersucht, die Möglichkeiten als "potentielles Feld" -Methodenangebot zu verbessern. Meine Herausforderung besteht darin, zu vermeiden, dass der Roboter in "lokalem Minimum" gefangen wird, wenn er die "potentielle Feld" -Methode verwendet. Anstatt einen "random walk" -Ansatz zu verwenden, um zu vermeiden, dass der Roboter in die Falle geht, habe ich darüber nachgedacht, ob es möglich ist, eine Variation von A * zu implementieren, die als eine Art Wegweiser dienen könnte, um zu vermeiden, örtliches Minimum ".

Gibt es einige der Erfahrungen dieser Art, oder kann auf Literatur verweisen, die lokale Minimum auf eine effektivere Weise vermeidet als die in der "Random-Walk" -Ansatz verwendet.

Answer 1

A * und potenzielle Felder sind alle Suchstrategien. Das Problem, das Sie haben, ist, dass einige Suchstrategien "gieriger" als andere sind, und in den meisten Fällen werden Algorithmen, die zu gierig sind, im lokalen Minimum gefangen. Es gibt einige Alternativen, bei denen die Spannung zwischen Gier (die Hauptursache für das Einfangen des lokalen Minimums) und Diversität (das Ausprobieren neuer Alternativen, die auf kurze Sicht keine gute Wahl zu sein scheinen) parametrisiert ist.

Vor ein paar Jahren habe ich ein wenig über Ameisenalgorithmen recherchiert (Suche nach Marco Dorigo, ACS, ACO) und sie haben eine Familie von Suchalgorithmen, die auf so ziemlich alles angewendet werden können, und sie können die Gier kontrollieren vs. Erkundung Ihres Suchraums. In einer ihrer Arbeiten verglichen sie sogar die Suchleistung, indem sie das TSP (das kanonische Problem des reisenden Verkäufers) mit Hilfe von genetischen Algorithmen, Simulated Annealing und anderen lösten. Ant hat gewonnen.

Ich habe die TSP in der Vergangenheit mit genetischen Algorithmen gelöst und ich habe immer noch den Quellcode in Delphi, wenn Sie möchten.

Answer 2

Verwenden Sie die Planungsplanung für harmonische Funktionen. Harmonische Funktionen sind potenzielle Funktionen, die den Flüssigkeitsstrom und andere natürliche Phänomene beschreiben. Wenn sie unter Verwendung von Randbedingungen korrekt eingerichtet sind, haben sie keine lokalen Minima. Diese werden seit den frühen 90ern von Rod Grupen and Chris Connolly verwendet. Es wurde gezeigt, dass diese Funktionen eine spezifische Form der optimalen Steuerung darstellen, die Kollisionswahrscheinlichkeiten minimiert. Sie können effizient in niederdimensionalen Räumen unter Verwendung von Differenzgleichungen (d. H. Gauß-Seidel, aufeinanderfolgende Überrelaxation usw.) berechnet werden.