Как избежать, чтобы робот был захвачен в локальном минимуме?
Я имею некоторое время, занимая меня с движением, планирующим роботы, и в течение некоторого времени хотел исследовать возможность улучшения возможностей как предложения метода "потенциального поля". Мой вызов состоит в том, чтобы избежать, чтобы робот был захвачен в "локальном минимуме" при использовании метода "потенциального поля". Вместо того, чтобы использовать подход "случайного блуждания", чтобы избежать, чтобы робот был захвачен, я думал о том, возможно ли реализовать изменение*, который мог бы действовать как своего рода руководство для точно, чтобы избежать, чтобы робот был захвачен в "локальном минимуме".
Есть ли некоторые события этого вида или могут относиться к литературе, которая избегает локального минимума более эффективным способом, чем тот, используемый в подходе "случайного блуждания".
1 ответ
A * и потенциальные поля - все стратегии поиска. Проблема, с которой вы столкнулись, заключается в том, что некоторые стратегии поиска более «жадны», чем другие, и чаще всего слишком жадные алгоритмы попадают в ловушку локального минимума.
Есть несколько альтернатив, в которых параметризовано противоречие между жадностью (основная причина попадания в ловушку локального минимума) и разнообразием (попыткой новых альтернатив, которые не кажутся хорошим выбором в краткосрочной перспективе).
Несколько лет назад я немного исследовал алгоритмы муравьев (поиск Марко Дориго, ACS, ACO), и у них есть семейство алгоритмов поиска, которые можно применить практически ко всему, и они могут контролировать жадность по сравнению с • исследование вашего поискового пространства. В одной из своих статей они даже сравнили эффективность поиска при решении TSP (канонической задачи коммивояжера) с использованием генетических алгоритмов, моделирования отжига и других. Муравей победил.
Я решал TSP в прошлом, используя генетические алгоритмы, и у меня все еще есть исходный код на delphi, если хотите.