Построить кривую траекторию в 2D системе координат
У меня есть несколько упорядоченных точек (менее 10) в 2D системе координат.
У меня есть агент, движущийся в системе и Я хочу найти кратчайший путь между этими точками, следуя их порядку.
В качестве фона агенту может быть предоставлена позиция, к которой он должен обращаться с толчком, и моя цель состоит в том, чтобы построить наиболее быстрый курс, учитывая тот факт, что агент имеет максимальную тягу и максимальную угловую скорость.
После некоторых исследований я понял, что, возможно, я ищу алгоритм подбора кривой, но я не знаю основную функцию, так как точки случайным образом распределены в системе координат.
Пожалуйста, помогите мне найти решение этой проблемы.
Я открыт для любых предложений, мой предпочтительный язык программирования — C ++.
Решение
Я уверен, что есть чисто математическое решение, такое как оптимизация траектории космического корабля, например, но вот как я мог бы подходить к этому с точки зрения программирования / отжига.
Несмотря на то, что вам нужен непрерывный путь, вы можете начать поиск пути с осторожных шагов и допусков для того, чтобы достаточно приблизиться к каждой точке в качестве начала.
- Назначьте определенное количество времени каждому шагу и варьируйте приложенное угловое усилие и тягу на каждом шаге.
- Рассчитать результирующий момент импульса и положение для начала следующего шага.
- Выберите параметры для следующего шага с помощью случайного поиска или выполните итерацию по каждому из них, чтобы найти ближайшую к следующей целевой точке (квантовать выбор углов и тяги для начала). Повторяйте шаги, пока не окажетесь достаточно близко к следующей целевой точке. Затем повторите, чтобы перейти к следующему пункту.
Если у вас есть грубый путь, вы можете начать его уточнять (возможно, использовать грубую точку из предыдущего цикла в качестве целевых точек в новом), уменьшив время / размер шагов и допуск к целевым точкам.
При оценке пригодности параметров на каждом шаге вы, возможно, захотите учесть, что, как только вы достигнете целевой точки, вы, возможно, захотите иметь импульс в направлении следующей точки. Это должно быть эмерджентным свойством, если учитывается несколько путей, а функция пригодности учитывает наименьшее общее время.
Здесь может помочь c ++, если вы используете std :: priority_queue и std :: map, например, чтобы отслеживать потенциальные пути.
Другие решения
Других решений пока нет …