Технический форум по робототехнике.
=DeaD= » 21 дек 2004, 23:57
Итак задачка!
Дано:1. Датчик расстояний на базе 2х веб-камер, определяющий расстояние до более чем 50% осмысленных фрагментов изображений, т.е. позволяющий построить более-менее адекватную модель видимой части пространства.
2. Мобильная (пусть для начала колесная, умеющая поворачиваться на месте) платформа, кроме того умеющая крутить головой (ну пусть 2 степени свободы сдвоенной камеры для сканирования пространства);
3. Доп. датчики, кроме GPS (и желательно кроме компаса);
Задача:Разработать алгоритм построения и постоянного дополнения карты, ориентации в пространстве (определения своего относительного расположения) с коррекцией своего местоположения по видимой части пространства, а также поиска пути и управления движением по нему из А в Б.
Ваши мысли в целом?
(завтра накидаю эскиз своего решения и темные места в нем)
=DeaD= » 24 дек 2004, 17:58
Вот и завтра наступило
Скелет алгоритма:
Инициализация после некоторого периода "в отключке", фактически процесс привязки к местности:
1. Принять текущее положение за точку отсчета;
2. Просканировать местность вокруг не перемещаясь;
3. Сопоставить с имеющимися в памяти картами - вдруг "очнулись" в знакомом месте, в случае обнаружения достаточных соответствий выбрать максимальное, как наиболее вероятную текущую гипотезу о карте, где мы находимся;
Процесс ориентирования в пространстве и пополнения информации о карте местности:
1. Совершить перемещение на малое расстояние;
2. Просканировать местность не перемещаясь полностью или частично;
3. Имея информацию о результатах сканирования местности и ожидаемом нашем перемещении рассчитать фактическое перемещение;
4. Обновить карту местности;
5. В случае наличия текущей гипотезы и обнаружения существенных расхождений текущей карты и карты гипотезы рассмотреть вариант о смене гипотезы или отказа от варианта "знакомая карта".
Темные места:
1. Сопоставление "похожести" на уже знакомую карту;
2. Определение фактического перемещения в пространстве;
3. Алгоритм объединения новой информации в текущую карту (при противоречиях и неполных данных);
4. Формат хранения текущей и старых карт;
Kanoka » 24 дек 2004, 20:24
Да, что и говорить, тема глобальная. Как по мне так это одно сплошное темное пятно. Я даже не совсем понимаю как робот определит свое местоположение даже если он находится на известной ему месности и у него есть карта (тоесть теоритически ясно, а практически нет).
Кстати помоему эти же задачи решала Стандфорская Тележка, в интернете не искал?
=DeaD= » 24 дек 2004, 20:39
Эскиз алгоритма определения того, что "находимся на известной местности":
Вариант номер раз - брутальный (полный) перебор - очень проблемен в трехмерном пространстве, учитывая что надо перебирать еще и 3 угла как минимум с шагом 5°.
Что можно сделать, чтобы облегчить задач - поставить на робота датчики углов наклона и компас, тогда углы перебирать не будет необходимости.
Тогда, в случае карты размера хотябы 50x50x20 - надо будет перебирать минимум 50'000 вариантов расположения, в каждом анализировать блок пространства хотя-бы размера 10х10х10 - итого 50'000'000 операций - не так уж много для современных ЭВМ, можно чуть-ли не в реальном времени делать, при небольшой оптимизации.
Вариант номер два - "feature-based" - надо научиться распознавать стабильные особенности в окружающем мире, и потом ориентироваться по ним, именно так делает человек. Тогда брутальный перебор падает до максимум 3-5 тыс операций и все ресурсы надо бросать на распознавание образов, т.е. "feature"-сов.
Kanoka » 24 дек 2004, 21:48
Как по мне второй вариант явно логичнее, научить робота запоминать 3-х мерные модели объектов и по ним уже потом ориеттироваться. Другое дело что в квартире все объекты могут перемещаться, на своих местах остаются только стены, из этого следует что ему (роботу) нужно научится отличать стену от шкафа например.
В принципе план пустой квартиры можно изначально в него записать, я думаю ничего страшного, далее по идее он должен сам разобратся что все объекты не отраженные на начальном плане являются мобильными, и некоторые из них могут быть перемещены в пространстве.
Исходя из того что шкафы меняют свое положение в квартире гораздо реже чем лежащий на полу мячик можно ввести некий индекс стабильности объекта. Например: стена имеет индекс 0, шкаф который робот с момента своего рождения обнаруживает неизвенно на одном и том же месте - индекс 1, а тот же мячик, или бесцельно слоняющийся по квартире кот, индекс 10, как исключительно нестабильный объект.
Далее, проснувшись робот обнаруживает что он стоит в метре от стены (как он поймет что это стена пока незнаю) и в 30 градусах, на растоянии полуметра от него находится объект который он идентифицирует как стул (коль он его узнал то должен и понять каким боком он к нему повернут)...
Рассуждения заходят в тупик :?
Воощем подумать еще нужно...
=DeaD= » 24 дек 2004, 21:55
Kanoka писал(а):Как по мне второй вариант явно логичнее, научить робота запоминать 3-х мерные модели объектов и по ним уже потом ориеттироваться. Другое дело что в квартире все объекты могут перемещаться, на своих местах остаются только стены, из этого следует что ему (роботу) нужно научится отличать стену от шкафа например.
Все гораздо хуже - первым же ходом возникает вопрос типа "Является ли объект А одним целым с объектом Б?", ответить на который не в состоянии ни один человек, первый раз видящий эти предметы...
Посему и предлагается явно внести некий вид особенностей, типа "точки повышенной стабильности", при этом такие точки можно сразу протоколировать. Очевидно к ним нужно относить угловые точки стен на полу и на потолке. Тогда останется один вопрос - что считать стеной...
setar » 27 дек 2004, 12:14
В каком виде 3D карту месности храним ?
а. векторная карта от "0" точки.
б. 3D составные простые объекты
с. сплэйны поверхности, как в некоторых играх - поверхность разбитая на малые элементарные треугольники.
д. может ещё варианты ?
=DeaD= » 27 дек 2004, 13:00
1. Обязательно (уже есть) вариант 3-х мерного массива из 0 и 1;
2. Варианты "а" и "с" совпадают вроде?
3. Сейчас думаю над тем, как бы распознать объекты или их фрагменты и сохранить их в векторном виде, но тут сразу мильон проблем с текстурами, а это уже высший пилотаж - в автоматическом режиме натягивать текстуры на трехмерные объекты с ошибками
Kanoka » 27 дек 2004, 15:33
Ну с текстурами это ты уже загнул наверное, нет можно и текстуру накладывать но исключительно одного цвета. Думаю должно хватить если исходить из примерно такого примера (стена - белая, шкаф - коричневый).
Сетар какой то новый метод в рисовании графики игрушек? Спрайты знаю, полигоны и воксели тоже, а о сплэйнах слышу в первый раз
=DeaD= » 27 дек 2004, 20:18
Видимо вместо сплайнов надо было сказать что-то типа NURBS-поверхности, но это опять же совсем уже высший пилотаж...
Еще кстати есть окто-деревья, их можно применять для хранения трехмерных карт в памяти. Но обрабатывать их меня не радует - отладки легко на 2-3 дня в каждой процедуре...
setar » 28 дек 2004, 14:30
Kanoka писал(а):Сетар какой то новый метод в рисовании графики игрушек? Спрайты знаю, полигоны и воксели тоже, а о сплэйнах слышу в первый раз
Видимо я что то напутал в названии.
Имел в виду рабзбиение поверхности на мелкие элементы.
Kanoka » 28 дек 2004, 14:40
Полигоны называются
=DeaD= » 12 янв 2005, 23:29
Идейка всплыла в воспаленном мозгу
Ориентирование по "верстовым столбам" для робота!
То есть:
1. На робота ставим веб-камеру;
2. По всей квартире расставляем "верстовые столбы" фиксированного размера - объекты под распознавание которых заточена система в роботе, которые кроме этого могут нести в виде некоторого "штрих-кода" дополнительную информацию, например номер маяка.
3. Тогда ориентирование в пространстве сводится к нахождению в изображении маяков, определению их на рисунке, определению приблизительного расстояния до них исходя из их размера, далее из памяти извлекаем координаты этого "столба" и шпарим
Как вам идея?
Реализуется 1 веб-камерой
Digit » 13 янв 2005, 00:28
А чем эта идея отличается от маячков? Ну, кроме использования непривычной и неожиданной для таких делов веб-камеры?
=DeaD= » 13 янв 2005, 00:34
Digit писал(а):А чем эта идея отличается от маячков? Ну, кроме использования непривычной и неожиданной для таких делов веб-камеры?
Тем что:
1. Веб-камера позволяет определять направление на маяк в двух углах с высокой точностью;
2. По размеру изображения маяка мы можем определить расстояние до него;
3. На маяке может быть размещена доп. информация в читаемом для робота виде;
4. Для веб-камеры это может быть совсем не единственная задача;
Скажите вы сможете без веб-камеры за 1сек просканировать большой объемный угол и достаточно точно определить координаты маяка в нем, если он там есть?
а описанное выше - теоретически может (завтра займусь опытами
)