roboforum.ru

Итак задачка!

Дано:
1. Датчик расстояний на базе 2х веб-камер, определяющий расстояние до более чем 50% осмысленных фрагментов изображений, т.е. позволяющий построить более-менее адекватную модель видимой части пространства.

2. Мобильная (пусть для начала колесная, умеющая поворачиваться на месте) платформа, кроме того умеющая крутить головой (ну пусть 2 степени свободы сдвоенной камеры для сканирования пространства);

3. Доп. датчики, кроме GPS (и желательно кроме компаса);

Задача:
Разработать алгоритм построения и постоянного дополнения карты, ориентации в пространстве (определения своего относительного расположения) с коррекцией своего местоположения по видимой части пространства, а также поиска пути и управления движением по нему из А в Б.

Ваши мысли в целом?
(завтра накидаю эскиз своего решения и темные места в нем)

Вот и завтра наступило

Скелет алгоритма:

Инициализация после некоторого периода "в отключке", фактически процесс привязки к местности:
1. Принять текущее положение за точку отсчета;
2. Просканировать местность вокруг не перемещаясь;
3. Сопоставить с имеющимися в памяти картами - вдруг "очнулись" в знакомом месте, в случае обнаружения достаточных соответствий выбрать максимальное, как наиболее вероятную текущую гипотезу о карте, где мы находимся;

Процесс ориентирования в пространстве и пополнения информации о карте местности:
1. Совершить перемещение на малое расстояние;
2. Просканировать местность не перемещаясь полностью или частично;
3. Имея информацию о результатах сканирования местности и ожидаемом нашем перемещении рассчитать фактическое перемещение;
4. Обновить карту местности;
5. В случае наличия текущей гипотезы и обнаружения существенных расхождений текущей карты и карты гипотезы рассмотреть вариант о смене гипотезы или отказа от варианта "знакомая карта".

Темные места:
1. Сопоставление "похожести" на уже знакомую карту;
2. Определение фактического перемещения в пространстве;
3. Алгоритм объединения новой информации в текущую карту (при противоречиях и неполных данных);
4. Формат хранения текущей и старых карт;

Да, что и говорить, тема глобальная. Как по мне так это одно сплошное темное пятно. Я даже не совсем понимаю как робот определит свое местоположение даже если он находится на известной ему месности и у него есть карта (тоесть теоритически ясно, а практически нет).

Кстати помоему эти же задачи решала Стандфорская Тележка, в интернете не искал?

Эскиз алгоритма определения того, что "находимся на известной местности":

Вариант номер раз - брутальный (полный) перебор - очень проблемен в трехмерном пространстве, учитывая что надо перебирать еще и 3 угла как минимум с шагом 5°.

Что можно сделать, чтобы облегчить задач - поставить на робота датчики углов наклона и компас, тогда углы перебирать не будет необходимости.

Тогда, в случае карты размера хотябы 50x50x20 - надо будет перебирать минимум 50'000 вариантов расположения, в каждом анализировать блок пространства хотя-бы размера 10х10х10 - итого 50'000'000 операций - не так уж много для современных ЭВМ, можно чуть-ли не в реальном времени делать, при небольшой оптимизации.

Вариант номер два - "feature-based" - надо научиться распознавать стабильные особенности в окружающем мире, и потом ориентироваться по ним, именно так делает человек. Тогда брутальный перебор падает до максимум 3-5 тыс операций и все ресурсы надо бросать на распознавание образов, т.е. "feature"-сов.

Как по мне второй вариант явно логичнее, научить робота запоминать 3-х мерные модели объектов и по ним уже потом ориеттироваться. Другое дело что в квартире все объекты могут перемещаться, на своих местах остаются только стены, из этого следует что ему (роботу) нужно научится отличать стену от шкафа например.
В принципе план пустой квартиры можно изначально в него записать, я думаю ничего страшного, далее по идее он должен сам разобратся что все объекты не отраженные на начальном плане являются мобильными, и некоторые из них могут быть перемещены в пространстве.
Исходя из того что шкафы меняют свое положение в квартире гораздо реже чем лежащий на полу мячик можно ввести некий индекс стабильности объекта. Например: стена имеет индекс 0, шкаф который робот с момента своего рождения обнаруживает неизвенно на одном и том же месте - индекс 1, а тот же мячик, или бесцельно слоняющийся по квартире кот, индекс 10, как исключительно нестабильный объект.
Далее, проснувшись робот обнаруживает что он стоит в метре от стены (как он поймет что это стена пока незнаю) и в 30 градусах, на растоянии полуметра от него находится объект который он идентифицирует как стул (коль он его узнал то должен и понять каким боком он к нему повернут)...

Рассуждения заходят в тупик  :?
Воощем подумать еще нужно...

Kanoka писал(а):Как по мне второй вариант явно логичнее, научить робота запоминать 3-х мерные модели объектов и по ним уже потом ориеттироваться. Другое дело что в квартире все объекты могут перемещаться, на своих местах остаются только стены, из этого следует что ему (роботу) нужно научится отличать стену от шкафа например.

Все гораздо хуже - первым же ходом возникает вопрос типа "Является ли объект А одним целым с объектом Б?", ответить на который не в состоянии ни один человек, первый раз видящий эти предметы...

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

В каком виде 3D карту месности храним ?

а. векторная карта от "0" точки.
б. 3D составные простые объекты
с. сплэйны поверхности, как в некоторых играх - поверхность разбитая на малые элементарные треугольники.
д. может ещё варианты ?

1. Обязательно (уже есть) вариант 3-х мерного массива из 0 и 1;
2. Варианты "а" и "с" совпадают вроде?
3. Сейчас думаю над тем, как бы распознать объекты или их фрагменты и сохранить их в векторном виде, но тут сразу мильон проблем с текстурами, а это уже высший пилотаж - в автоматическом режиме натягивать текстуры на трехмерные объекты с ошибками

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

Сетар какой то новый метод в рисовании графики игрушек? Спрайты знаю, полигоны и воксели тоже, а о сплэйнах слышу в первый раз

Видимо вместо сплайнов надо было сказать что-то типа NURBS-поверхности, но это опять же совсем уже высший пилотаж...

Еще кстати есть окто-деревья, их можно применять для хранения трехмерных карт в памяти. Но обрабатывать их меня не радует - отладки легко на 2-3 дня в каждой процедуре...

Kanoka писал(а):Сетар какой то новый метод в рисовании графики игрушек? Спрайты знаю, полигоны и воксели тоже, а о сплэйнах слышу в первый раз

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

Полигоны называются

Идейка всплыла в воспаленном мозгу

Ориентирование по "верстовым столбам" для робота!

То есть:
1. На робота ставим веб-камеру;
2. По всей квартире расставляем "верстовые столбы" фиксированного размера - объекты под распознавание которых заточена система в роботе, которые кроме этого могут нести в виде некоторого "штрих-кода" дополнительную информацию, например номер маяка.
3. Тогда ориентирование в пространстве сводится к нахождению в изображении маяков, определению их на рисунке, определению приблизительного расстояния до них исходя из их размера, далее из памяти извлекаем координаты этого "столба" и шпарим  

Как вам идея?

Реализуется 1 веб-камерой

А чем эта идея отличается от маячков? Ну, кроме использования непривычной и неожиданной для таких делов веб-камеры?

Digit писал(а):А чем эта идея отличается от маячков? Ну, кроме использования непривычной и неожиданной для таких делов веб-камеры?

Тем что:
1. Веб-камера позволяет определять направление на маяк в двух углах с высокой точностью;
2. По размеру изображения маяка мы можем определить расстояние до него;
3. На маяке может быть размещена доп. информация в читаемом для робота виде;
4. Для веб-камеры это может быть совсем не единственная задача;

Скажите вы сможете без веб-камеры за 1сек просканировать большой объемный угол и достаточно точно определить координаты маяка в нем, если он там есть? а описанное выше - теоретически может (завтра займусь опытами )