Войти
ПроектыФорумУтилиты

[|---------9%----------] 2D Планировщик траекторий v.2016

Страницы: 1 2 Следующая »
#0
11:01, 28 мая 2016

Название: 2D Планировщик траекторий v.2016
Жанр: Top-Down Планировщик траекторий
Разработчики: Adler
Платформа: Win32
Технологии: QapLite
Скачать: *** недоступно широкой публике(в этом месяце) ***
Предзаказ: пока тут // «плати сколько хочешь и чем хочешь»

Научился перебором планировать траекторию движения транспортного средства движущегося с постоянной по модулю скорость в сложном геометрическом пространстве с препятствиями.

Не знаю зачем, просто взял и сделал:

+ new

map20160805 | [|---------9%----------] 2D Планировщик траекторий v.2016
map20160607 | [|---------9%----------] 2D Планировщик траекторий v.2016
видео ускрено(7x)


В дальнейшем планирую использовать следующее поколения этого обобщеного планировщика траекторий для анализа/оценки сгенерированого помещения или транспортной сети.


А это что за петля? (C)MrShoor
path | [|---------9%----------] 2D Планировщик траекторий v.2016

- Это фрагмент зелёной траектории. // Цель этой траектории - приехать в заданную точку пространства в заданом направлении.

Спасибо за внимание.


#1
11:12, 28 мая 2016

Круто, че

#2
11:37, 28 мая 2016

Adler
> Это фрагмент зелёной траектории. // Цель этой траектории - приехать в заданную
> точку пространства в заданом направлении.
Что-то мне подсказывает, что можно намного быстрее приехать:
newpath | [|---------9%----------] 2D Планировщик траекторий v.2016

#3
12:40, 28 мая 2016

MrShoor
Спасибо, похоже ты прав:
Бдительность | [|---------9%----------] 2D Планировщик траекторий v.2016
Петля тут не нужна.

Прога ограничена по CPU time и RAM, поэтому результат её работы в общем случае годиться только для нахождения хоть каких-нибудь траекторий к цели.
Если поправить несколько констант и дать проге больше времени и памяти, то я уверен она найдёт и будет выдавать тут траекторию без петли.

#4
14:13, 28 мая 2016

Пффффф, обычный волновой алгоритм.

#5
14:55, 28 мая 2016

AntonioModer
> Пффффф, обычный волновой алгоритм.
считаешь, что реализация алгоритма даже на название "модифицированый волновой алгоритм" не тянет?
wave | [|---------9%----------] 2D Планировщик траекторий v.2016

#6
15:41, 28 мая 2016

Adler
Тянет

#7
17:33, 28 мая 2016

Adler
слишком криво работает. 

#8
17:25, 9 июня 2016

О, серьёзные намерения, однако.

Вопросы:
- Какой вектор состояния? {x;y;angle} или {x;y} с проверкой валидности радиуса поворота?
- Насколько дискретны координаты. Состояния округляются по сетке, или свободно плавают в пределах ячейки?

#9
20:51, 9 июня 2016

frost
> Какой вектор состояния?
{x;y;angle}
frost
> - Насколько дискретны координаты. Состояния округляются по сетке, или свободно
> плавают в пределах ячейки?
double. Узлы дерева траекторий свободно плавают в пределах ячейки.

Ячейки - это побочный эффект появившийся при оптимизации алгоритма, без них количество узлов в дереве траекторий растёт по экспоненте.
#10
22:34, 9 июня 2016

О, отлично, проецируешь состояния значит, дабы их сравнить и отсечь плохие варианты. Какой шаг времени? Как семплишь новые состояния?

#11
23:00, 9 июня 2016

В той версии что на скриноштах и видео - 64UPS, каждые n-апдейтов фронтовые узлы ветвятся, а затем сразу же симулируются на n-апдейтов вперёд. Потом новые выжившие узлы если пространство в их ячейке не занятно намного лучшей траекторией записываются в новый фронт волны. Значения в ячейках обновляются вот тут - ",а затем сразу же симулируются на n-апдейтов вперёд." на каждом апдейте.

#12
23:25, 9 июня 2016

Давай подробнее про ветвление. Что за 64UPS?
>фронтовые узлы ветвятся
Вот как раз этот процесс интересен. Рандомно раскидываешь N состояний вокруг текущего состояния, и проверяешь габариты и элементарный путь между ними (dubins car)? Или что-то типа control-based sampling, в твоём случае это варьирование угловой скорости (линейная скорость постоянная максимальная) и симуляция новых состояний через следующий dT?
Какое N при этом? Какое dT или размеры области, в которой генеришь новые состояния (относительно размера ячеек)?

#13
0:59, 10 июня 2016

У меня похоже control-based sampling. Один фронтовой узел порождает 3 дочерних с варьирование угловой скорости: -W,0,+W. Рандома нет. Каждый узел владеет куском траектории(n-апдейтов) с постоянной угловой скоростью.
>Какое N при этом?
Я точно не помню, сначала было 16, потом было 8. Потом я пробовал делать 4, но что-то мне тогда не понравилось и я увеличил до 6. На чём остановился не помню, наверно на 4. Я хотел чтобы карта выглядела как можно круче и квадратики были поменьше. А вспомнил, у меня поначалу при N=4 ОЗУ заканчивалось + отрисовка карты сильно тормозила + размера вершинного буфера не хватало, но потом я всё исправил.
> Какое dT или размеры области, в которой генеришь новые состояния (относительно
> размера ячеек)?
Я при старте программы подбираю размер ячейки так, чтобы за n-апдейтов конец траектории{pos:vec2d(0,0);ang:0;w:+W} отклонился от оси OX на размер ячейки.
Я неверно не сильно ошибусь если скажу что "область генерации состояний" для одного узла где-то от 3 до 5 ячеек.

Я когда делал алгоритм не хотел привязываться к конкретной задаче симулировании какого-то одного убогого транспортного средства. Поэтому траектория - это просто последовательность управляющих воздействий. И задача алгоритма - перебрать их все.
64UPS = 64 Updates per second.
#14
9:45, 10 июня 2016

Ага.
Проецируешь на 2d грид {x;y} или 3д {x;y;angle}? Если первый случай, то ровно от этого поиск и промахивается мимо оптимального маршрута. Такие проецирования из пространства состояний с большей размерностью в меньшую портят оптимальность, хотя и прибавляют производительности. Проецирование в дискретные ячейки (даже при сохранении float координат) тоже портит блюдо, но уже в крайне ограниченой области (размеров ячейки)

Страницы: 1 2 Следующая »
ПроектыФорумУтилиты

Тема в архиве.