roboforum.ru

Технический форум по робототехнике.

Прицеливание. Ведение огня.

Автомат, адаптивный автомат ... разум

Прицеливание. Ведение огня.

Сообщение Виталий » 07 авг 2007, 22:57

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

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

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

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

Пример целей:
Изображение

Видео работы аналогичного робота:
http://defconbots.org/defcon14/20060326 ... _small.avi
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Сообщение Master » 07 авг 2007, 23:10

[off]Идей валом. Времени нет. А когда время есть, то лень. Это у всех так или я один такой особенный?[/off]
Короче тебе нужен проект Diana, там рассказывается как сделать дальномер на основе Web-камеры. А дальше крепишь камеру на орудие и вперед. Тока нада чтоб мишени выделялись на фоне, ну были там красные.
Тока я не совсем понял там на видео в одну мишень целая обойма. Лучше один выстрел - один труп.
Аватара пользователя
Master
 
Сообщения: 4468
Зарегистрирован: 21 дек 2006, 19:56
Откуда: Украина, г.Одесса
прог. языки: Delphi и С

Сообщение Виталий » 08 авг 2007, 00:01

там рассказывается как сделать дальномер

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

Тока нада чтоб мишени выделялись на фоне, ну были там красные.

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

Тока я не совсем понял там на видео в одну мишень целая обойма. Лучше один выстрел - один труп.

Системы ПВО так и работают, расход патронов не принципиален.
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Сообщение Master » 08 авг 2007, 19:41

Чета я не понял, если все известно, то в чем проблема? Расстояние одинаковое значит поправка на высоту одинаковая.
Аватара пользователя
Master
 
Сообщения: 4468
Зарегистрирован: 21 дек 2006, 19:56
Откуда: Украина, г.Одесса
прог. языки: Delphi и С

Сообщение SSG » 08 авг 2007, 21:12

Если всё известно, то расчет углов - чистой воды физика+дополнение из поправок, обусловленных сопротивлением воздуха. А снаряд у вас не вращается? А то тоже поправку нужно вводить. Как я понял нужен алгоритм, который позволял бы погасить мишени с наименьшими временными затратами по ориентированию пушки. Может быть тут поможет математическое моделирование (отдаленно напоминает задачу коммивояжера)?
Аватара пользователя
SSG
 
Сообщения: 1058
Зарегистрирован: 15 янв 2007, 19:23
Откуда: Беларусь, Барановичи
прог. языки: С для МК, Delphi для ПК

Сообщение Виталий » 09 авг 2007, 00:35

Может быть тут поможет математическое моделирование (отдаленно напоминает задачу коммивояжера)?


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

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

И последний вопрос, у кого-нибудь хватило бы смелости реализовать подобный алгоритм?
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Сообщение SSG » 09 авг 2007, 23:55

Виталий писал(а):Если второе, то хотелось бы узнать как можно смоделировать поправку на движение?

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

Идейно и теоретически помочь могу. Целиком (на программирование) - нет времени. Хотя... :)
Аватара пользователя
SSG
 
Сообщения: 1058
Зарегистрирован: 15 янв 2007, 19:23
Откуда: Беларусь, Барановичи
прог. языки: С для МК, Delphi для ПК

Сообщение =DeaD= » 12 авг 2007, 22:46

Если мы говорим чисто про алгоритм выбора порядка обработки целей, то задача эквивалентна задаче коммивояжора (только функция расстояния специфическая = максимуму модулей разности), которая на 100% может решаться только полным перебором. Насколько я знаю, существуют алгоритмы, позволяющие найти за разумное время решение, близкое к оптимальному с точностью до константы.
Последний раз редактировалось =DeaD= 12 авг 2007, 22:51, всего редактировалось 1 раз.
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Сообщение Master » 12 авг 2007, 22:48

Я думаю для начала можно сделать просто как развертка в телевизоре.
Аватара пользователя
Master
 
Сообщения: 4468
Зарегистрирован: 21 дек 2006, 19:56
Откуда: Украина, г.Одесса
прог. языки: Delphi и С

Сообщение =DeaD= » 12 авг 2007, 22:53

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

Задача коммивояжера в общей википедии: 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 (там внизу ссылка на приближенное решение метрической версии алгоритмом Кристофидеса - это для вас как раз, у вас именно метрическая версия с такой функцией расстояния).
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Сообщение SSG » 13 авг 2007, 01:02

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

Ну тогда хотя бы и на обратном пути тоже стрелять.
Аватара пользователя
SSG
 
Сообщения: 1058
Зарегистрирован: 15 янв 2007, 19:23
Откуда: Беларусь, Барановичи
прог. языки: С для МК, Delphi для ПК

Сообщение Master » 13 авг 2007, 01:08

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

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

А что телек тока в одну сторону рисует?
Аватара пользователя
Master
 
Сообщения: 4468
Зарегистрирован: 21 дек 2006, 19:56
Откуда: Украина, г.Одесса
прог. языки: Delphi и С

Сообщение SSG » 13 авг 2007, 11:00

Master писал(а):А что телек тока в одну сторону рисует?

[off]Ну да. Вот, например, в самом простом случае примитивного осциллографа прогон луча осуществляется пилообразным наприжением.  :roll: [/off]
А вообще методов решения задачи коммивояжера много. Тут и графы можно привлечь, и генетические алгоритмы. А вообще алгоритмы грубо можно разделить на 2 вида:
1) точные, которые позволяют найте абсолютно точное или наиболее лучшее решение. В задаче коммивояжера это метод перебора.
2) приближенные, которые позволяют найти "хорошее решение" за некоторое ограниченное время. К ним можно отнести, например, генетические алгоритмы. Вот, к примеру, задачу составления расписания в учебном заведении очень сложно решить "точно", т.е. получить абсолютно удовлетворящее всех расписание. Но достаточно хорошее, с некоторыми допущениями, получить можно достаточно быстро (при наличии нужного софта и головы :D).
Какой алгоритм выбрать для решения конкретной задачи зависит от начальных условий. В данном случае, если мишеней немного и хватает вычислительной мощности, то простой перебор можно осуществить оч. быстро и не нежно будет лезть в дебри мат. моделирования.  :D
Аватара пользователя
SSG
 
Сообщения: 1058
Зарегистрирован: 15 янв 2007, 19:23
Откуда: Беларусь, Барановичи
прог. языки: С для МК, Delphi для ПК

Сообщение KiCom » 13 авг 2007, 18:23

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

Сообщение lebaon » 13 авг 2007, 20:27

а может наводить на ближнюю цель к текущей линии наводки? по оптимальности конечно хуже, чем перебор,
зато по скорости :twisted:
Аватара пользователя
lebaon
Безбашенный Теоретик
 
Сообщения: 1137
Зарегистрирован: 07 янв 2006, 18:30
Откуда: Подмосковье

След.

Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1