roboforum.ru

Я потихонечку подготавливаю проект стреляющего робота на defconbots.org
Напомню, что недавно выложил описание: http://www.roboforum.ru/viewtopic.htm?t=2841

Итак стоит задача создания системы прицеливания и ведения огня. Вот как она выглядит в моем случае...

- Есть орудие управляемое по азимуту и углу (наклону).
- Известна начальная скорость и вес пули.
- Инерцией орудия можно пренебречь.
- Известна максимальная и минимальная скорость управления орудием по азимуту и по углу.
- Известны координаты целей на экране.

Задача: разработать алгоритм позволяющий как можно быстрее поразить все цели. Есть идеи?

Пример целей:


Видео работы аналогичного робота:
http://defconbots.org/defcon14/20060326 ... _small.avi

_________________
Все новости о моих проектах http://savethebest.ru

[off]Идей валом. Времени нет. А когда время есть, то лень. Это у всех так или я один такой особенный?[/off]
Короче тебе нужен проект Diana, там рассказывается как сделать дальномер на основе Web-камеры. А дальше крепишь камеру на орудие и вперед. Тока нада чтоб мишени выделялись на фоне, ну были там красные.
Тока я не совсем понял там на видео в одну мишень целая обойма. Лучше один выстрел - один труп.

Мне не нужен дальномер расстояние до целей известно.


Мы считаем, что мишени уже выделены и их координаты известны. Благо как решить эту задачу я знаю.


Системы ПВО так и работают, расход патронов не принципиален.

_________________
Все новости о моих проектах http://savethebest.ru

Чета я не понял, если все известно, то в чем проблема? Расстояние одинаковое значит поправка на высоту одинаковая.

Если всё известно, то расчет углов - чистой воды физика+дополнение из поправок, обусловленных сопротивлением воздуха. А снаряд у вас не вращается? А то тоже поправку нужно вводить. Как я понял нужен алгоритм, который позволял бы погасить мишени с наименьшими временными затратами по ориентированию пушки. Может быть тут поможет математическое моделирование (отдаленно напоминает задачу коммивояжера)?

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

Двигаться и останавливаться в момент выстрела?
Или стрелять во время движения?
Если второе, то хотелось бы узнать как можно смоделировать поправку на движение?

И последний вопрос, у кого-нибудь хватило бы смелости реализовать подобный алгоритм?

_________________
Все новости о моих проектах http://savethebest.ru

Вряд ли она понадобится, если вылет снаряда будет происходить в нужное время.

Идейно и теоретически помочь могу. Целиком (на программирование) - нет времени. Хотя...

Если мы говорим чисто про алгоритм выбора порядка обработки целей, то задача эквивалентна задаче коммивояжора (только функция расстояния специфическая = максимуму модулей разности), которая на 100% может решаться только полным перебором. Насколько я знаю, существуют алгоритмы, позволяющие найти за разумное время решение, близкое к оптимальному с точностью до константы.

Я думаю для начала можно сделать просто как развертка в телевизоре.

Ссылочки по существу темы:

Задача коммивояжера в общей википедии: http://ru.wikipedia.org/wiki/%D0%97%D0% ... 1%80%D0%B0

В специализированной вики: http://lib.custis.ru/index.php/%D0%97%D ... 1%80%D0%B0 (там внизу ссылка на приближенное решение метрической версии алгоритмом Кристофидеса - это для вас как раз, у вас именно метрическая версия с такой функцией расстояния).

Ну тогда хотя бы и на обратном пути тоже стрелять.

А что телек тока в одну сторону рисует?

[off]Ну да. Вот, например, в самом простом случае примитивного осциллографа прогон луча осуществляется пилообразным наприжением.  :roll: [/off]
А вообще методов решения задачи коммивояжера много. Тут и графы можно привлечь, и генетические алгоритмы. А вообще алгоритмы грубо можно разделить на 2 вида:
1) точные, которые позволяют найте абсолютно точное или наиболее лучшее решение. В задаче коммивояжера это метод перебора.
2) приближенные, которые позволяют найти "хорошее решение" за некоторое ограниченное время. К ним можно отнести, например, генетические алгоритмы. Вот, к примеру, задачу составления расписания в учебном заведении очень сложно решить "точно", т.е. получить абсолютно удовлетворящее всех расписание. Но достаточно хорошее, с некоторыми допущениями, получить можно достаточно быстро (при наличии нужного софта и головы ).
Какой алгоритм выбрать для решения конкретной задачи зависит от начальных условий. В данном случае, если мишеней немного и хватает вычислительной мощности, то простой перебор можно осуществить оч. быстро и не нежно будет лезть в дебри мат. моделирования.  :D

Перебором какой-бы мощной системой не был считать будет ооочень долго. На рисунке 20 мишеней число вариантов 20! это число с 15 знаками. Можно взять 1000 случайных маршрутов расчитать их и выбрать самый короткий.
Однако тут нужно учитывать параметры двигателей. Если ускорение которое могут создать двигатели маленькое, то как мне кажется оптимальным будет движение по спирали.

а может наводить на ближнюю цель к текущей линии наводки? по оптимальности конечно хуже, чем перебор,
зато по скорости