Как избежать попадания робота в локальный минимум?
Я какое-то время занимался планированием движения для роботов и некоторое время хотел изучить возможность улучшения возможностей, предлагаемых методом "потенциального поля". Моя задача - избежать попадания робота в "локальный минимум" при использовании метода "потенциального поля". Вместо того, чтобы использовать подход "случайного блуждания", чтобы избежать попадания робота в ловушку, я подумал о том, можно ли реализовать вариант A*, который мог бы служить своего рода руководством для того, чтобы точно не попасть в ловушку робота ". местный минимум ".
Имеется ли какой-либо опыт такого рода, или можно сослаться на литературу, которая позволяет избежать локального минимума более эффективным способом, чем тот, который используется в подходе "случайного блуждания".
2 ответа
A* и потенциальные поля - все стратегии поиска. Проблема, с которой вы сталкиваетесь, заключается в том, что некоторые стратегии поиска являются более "жадными", чем другие, и чаще всего слишком жадные алгоритмы оказываются в ловушке локального минимума.
Существуют некоторые альтернативы, где параметризовано напряжение между жадностью (основной причиной попадания в ловушку локального минимума) и разнообразием (пробуя новые альтернативы, которые не кажутся хорошим выбором в краткосрочной перспективе).
Несколько лет назад я немного изучил муравьиные алгоритмы (поиск Марко Дориго, ACS, ACO), и у них есть семейство поисковых алгоритмов, которые можно применять практически ко всему, и они могут контролировать жадность и исследование Ваше пространство поиска. В одной из своих статей они даже сравнили эффективность поиска при решении TSP (канонической задачи коммивояжера) с использованием генетических алгоритмов, имитации отжига и других. Муравей победил.
Я решил TSP в прошлом, используя генетические алгоритмы, и у меня все еще есть исходный код на Delphi, если хотите.
Используйте планирование пути гармонической функции. Гармонические функции - это потенциальные функции, которые описывают течение жидкости и другие природные явления. Если они настроены правильно с использованием граничных условий, то у них нет локальных минимумов. Они используются с начала 90-х годов Родом Групеном и Крисом Коннолли. Было показано, что эти функции являются специфической формой оптимального управления, которая минимизирует вероятность столкновения. Они могут быть эффективно вычислены в пространствах с низкими измерениями с использованием разностных уравнений (т. Е. Гаусс-сейделя, последовательной избыточной релаксации и т. Д.).