Как избежать попадания робота в локальный минимум?

Question

Я некоторое время занимался планированием движения для роботов, и некоторое время хотел изучить возможность улучшения возможностей, предлагаемых методом «потенциального поля». Моя задача - избежать попадания робота в «локальный минимум» при использовании метода «потенциального поля». Вместо того чтобы использовать подход «случайного блуждания», чтобы избежать попадания робота в ловушку, я подумал о том, можно ли реализовать вариант A *, который мог бы служить своего рода руководством для того, чтобы точно не попасть в ловушку робота ». локальный минимум ".

Имеется ли какой-либо опыт такого рода, или он может относиться к литературе, которая позволяет избежать локального минимума более эффективным способом, чем тот, который используется в подходе "случайного блуждания".

Answer 1

A * и потенциальные поля - все стратегии поиска. Проблема, с которой вы столкнулись, состоит в том, что некоторые стратегии поиска являются более «жадными», чем другие, и чаще всего слишком жадные алгоритмы оказываются в ловушке локального минимума.

Существуют некоторые альтернативы, где параметризована напряженность между жадностью (основной причиной попадания в ловушку локального минимума) и разнообразием (пробуя новые альтернативы, которые не кажутся хорошим выбором в краткосрочной перспективе).

Несколько лет назад я немного исследовал алгоритмы муравья (поиск Марко Дориго, ACS, ACO), и у них есть семейство поисковых алгоритмов, которые можно применять практически ко всему, и они могут контролировать жадность против исследование вашего пространства поиска. В одной из своих статей они даже сравнили эффективность поиска при решении TSP (канонической задачи коммивояжера) с использованием генетических алгоритмов, имитации отжига и других. Муравей победил.

В прошлом я решал TSP с использованием генетических алгоритмов, и у меня все еще есть исходный код на Delphi, если хотите.

Answer 2

Использовать гармоническое планирование функций. Гармонические функции - это потенциальные функции, которые описывают течение жидкости и другие природные явления. Если они настроены правильно с использованием граничных условий, то у них нет локальных минимумов. Они используются с начала 90-х годов Родом Групеном и Крисом Коннолли . Было показано, что эти функции являются специфической формой оптимального управления, которая минимизирует вероятность столкновения. Они могут быть эффективно вычислены в пространствах с низкими измерениями с использованием разностных уравнений (т.е. гаусс-сейдель, последовательная избыточная релаксация и т. Д.).