Сканирование местности роботом

[Belzebub 0]

Хочу написать робота который будет сканировать местность по двум координатам ширина/длинна.
При первом запуске робот будет бегать по всем блокам и сохранять инфу для дальнейшей навигации.
Есть комната абстрактной формы и размеров, детоурнутые функции поворота/передвижения робота для подсчёта виртуального угола и позиции робота которые считается относительно стартовой позиции/угла.

Как заставить робота обойти все доступные блоки?

[eu_tomat 2 154]

Я плохо понял смысл задачи и вопроса.

 

1 час назад, Belzebub сказал:

Хочу написать робота который будет сканировать местность по двум координатам ширина/длинна. При первом запуске робот будет бегать по всем блокам и сохранять инфу для дальнейшей навигации.

Местность можно сканировать с помощью геосканера с минимальными движениями робота.

Или цель заключается именно в сканировании местности без геосканера?

 

1 час назад, Belzebub сказал:

Есть комната абстрактной формы и размеров

А робот тоже абстрактный? Потому что конкретные роботы, например, имеют ограниченный объём памяти.

 

1 час назад, Belzebub сказал:

детоурнутые функции поворота/передвижения робота

Какие функции?

 

1 час назад, Belzebub сказал:

Как заставить робота обойти все доступные блоки?

Легко: достаточно лишь написать соответствующую программу. Или надо конкретизировать вопрос.

[Belzebub Автор вопроса 0]

11 час назад, Belzebub сказал:

Как заставить робота обойти все доступные блоки?

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

9 часов назад, eu_tomat сказал:

Какие функции?

robot.turnRight/robot.turnLeft/robot.forward/robot.backward/e.t.c
что-бы считать виртуальную позицию робота относительно ориджина запуска робота.
 

9 часов назад, eu_tomat сказал:

А робот тоже абстрактный? Потому что конкретные роботы, например, имеют ограниченный объём памяти.

Абстрактны только условия в которые помещён робот (ширина и размер комнаты и позиция/угол робота при запуске), а компонетны можно и конкретизировать.

 

9 часов назад, eu_tomat сказал:

Местность можно сканировать с помощью геосканера с минимальными движениями робота.

Или цель заключается именно в сканировании местности без геосканера?

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

Изменено 13 декабря, 2021 пользователем Belzebub

[Zer0Galaxy 2 187]

Почему вообще возникла такая задача? Имеется практическая цель или академический интерес?

Должен ли робот сканировать блоки, находящиеся над/под ним или только в плоскости перемещения?

[eu_tomat 2 154]

4 часа назад, Belzebub сказал:

не пойму как написать прогу для обхода всей комнаты (неизвестный размер и форма комнаты, неизвестная стартовая позиция и угол робота и тд. робот должен пройтись по всем доступным блокам по 2d координатам и вернуться на стартовую позицию. комната 2d, замкнутая стенами.)

Если говорить коротко, то любая сложная задача решается её дроблением на задачи меньшего размера. Дробить задачи следует до тех пор, пока их решение не станет очевидным. Дело осложняется тем, что каждую из подзадач можно решить разными способами, имеющими свои преимущества и недостатки.

 

На какие основные блоки можно разделить нашу задачу?

• Обязательно потребуется способ определения текущего положения робота. Эту задачу можно с помощью расширения навигации, либо программным трекингом. В первом случае имеется уже готовый трекинг из коробки, но он ограничен квадратом какого-то размера в зависимости от выбранной карты. Второй способ практически не имеет ограничений, но требует аккуратного программирования.
• Потребуется выбрать способ определения блока. Геосканер поможет определить плотность блока на расстоянии, и более подробную информацию о блоке при непосредственном контакте. Функция robot.detect() позволит определить наличие блока непосредственно перед роботом, а robot.compare() кроме этого позволяет сравнить блок перед роботом с предметом в его инвентаре.
• Потребуется алгоритм обхода комнаты. Универсального оптимального алгоритма не существует. В зависимости от возможных конфигураций комнаты будет эффективен тот или иной алгоритм. Например, можно сначала двигаться до ближайшего препятствия, а потом двигаться так, чтобы препятствие всегда оказывалось справа от робота. Такой способ позволит быстро обойти периметр стены, но он плохо применим для комнат в внутренними препятствиями, например, с колоннами. Поэтому может потребоваться сплошной обход комнаты с полным построением карты пространства. Такой обход будет медленнее, и потребует большого количества памяти. Кстати, не факт, что вся карта одновременно поместится в оперативной памяти робота. Тогда потребуется ещё и придумать способ разделения карты на сегменты.

 

4 часа назад, Belzebub сказал:

Абстрактны только условия в которые помещён робот (ширина и размер комнаты и позиция/угол робота при запуске), а компонетны можно и конкретизировать.

Абстрактные задачи решают математики, и найденные ими решения должны работать хотя бы в теории.

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

Имея ограниченный объём памяти, робот даже теоретически не сможет построить карту любой абстрактной комнаты.

[Zer0Galaxy 2 187]

6 минут назад, eu_tomat сказал:

Имея ограниченный объём памяти, робот даже теоретически не сможет построить карту любой абстрактной комнаты.

Предлагаю сделать предположение, что размеры комнаты не превышают 100х160. Если какой либо участок комнаты вылезет за эти рамки, робот его проигнорирует. Почему именно 100х160? Да просто такую комнату можно будет отрисовать полупикселями на мониторе 3-его уровня.

[Belzebub Автор вопроса 0]

54 минуты назад, Zer0Galaxy сказал:

Почему вообще возникла такая задача? Имеется практическая цель или академический интерес?

Должен ли робот сканировать блоки, находящиеся над/под ним или только в плоскости перемещения?

академический интерес.

 

34 минуты назад, Zer0Galaxy сказал:

Предлагаю сделать предположение, что размеры комнаты не превышают 100х160. Если какой либо участок комнаты вылезет за эти рамки, робот его проигнорирует. Почему именно 100х160? Да просто такую комнату можно будет отрисовать полупикселями на мониторе 3-его уровня.

собственно это я и хотел, сканировать комнату и вывести её 2d проекцию на монитор робота.

[Zer0Galaxy 2 187]

В таком случае предлагаю следующий алгоритм:

1. Создаем массив 100х160, который будет хранить статусы блоков в нашей комнате.

Статусы могут быть следующие:

   -2 (неинтересно) - такой статус имеет блок, о котором пока не известно, находится ли он в пределах комнаты

   -1 (неизвестно) - такой статус имеет еще неисследованный блок, но о котором известно, что он в комнате или является ее стенкой

  0 (пусто) - пустое пространство внутри комнаты

  >0 - исследованный блок внутри комнаты или ее стенка. Может принимать значение равное номеру слота робота, с которым выполнилось сравнение.

2. Заполняем массив статусом "неинтересно". Считаем что робот находится в позиции X=80, Y=50 (центр нашего массива).

3. Присваиваем этой клетке статус "пусто". Просматриваем четыре, граничащие с ней клетки. Если они находятся в пределах массива и имеют статус "неинтересно", присваиваем им статус "неизвестно".

4. Ищем в массиве ближайшую клетку со статусом "неизвестно". Если таких клеток нет - конец работы

5. Иначе, перемещаемся к ней и исследуем.

6. Если она пустая, переходим к пункту 3

7. Иначе, присваиваем клетке тип блока. Переходим к пункту 4

 

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

[eu_tomat 2 154]

1 час назад, Zer0Galaxy сказал:

Создаем массив 100х160

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

1 час назад, Zer0Galaxy сказал:

Считаем что робот находится в позиции X=80, Y=50

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

[Syabro 81]

В 13.12.2021 в 12:12, Zer0Galaxy сказал:

Ищем в массиве ближайшую клетку со статусом "неизвестно". Если таких клеток нет - конец работы

А чего так сложно? А как он доберется, если посреди комнаты препятствие?

Отсканировать нормально комнату не выйдет по причине возможных замкнутых пространств в двумерном измерении. Внутрь он просто не попадет.

Тем не менее простым способом добиться хоть какого-то результата является правило левой руки (или правой).

1. Робот двигается до упора.

2. Поворачивается к препятствию левой рукой

3. Двигаемся вперёд проверяя препятствие спереди и слева

4. Если препятствия слева нет, поворачиваем налево, переходим к пункту 3

5. Иначе, если есть препятствие спереди, переходим к пункту 2

Такое правило поможет нарисовать контур, полагаю, если не ошибся

Также есть правило прохождения лабиринта А* вроде, чи то не то

А вообще геоанализатор в помощь.

 

Изменено 15 декабря, 2021 пользователем Syabro

[Syabro 81]

А камер с Computronics нет? 😅

Изменено 15 декабря, 2021 пользователем Syabro

[eu_tomat 2 154]

49 минут назад, Syabro сказал:

Тем не менее простым способом добиться хоть какого-то результата является правило левой руки (или правой).

1. Робот двигается до упора.

...

Автор вопроса не конкретизировал, что за комнаты требуется сканировать. Поэтому такой алгоритм не всегда применим:

В 13.12.2021 в 11:46, eu_tomat сказал:

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

 

 

[Syabro 81]

@eu_tomat Не заметил, извиняюсь

[Zer0Galaxy 2 187]

1 час назад, Syabro сказал:

В 13.12.2021 в 12:12, Zer0Galaxy сказал:

Ищем в массиве ближайшую клетку со статусом "неизвестно". Если таких клеток нет - конец работы

А чего так сложно? А как он доберется, если посреди комнаты препятствие?

"Ищем в массиве" это поиск в памяти. Тут никуда добираться не надо. А вот что бы проложить к ней путь и потребуется А*, не спорю.

1 час назад, Syabro сказал:

правило левой руки

Так мы просканируем только контуры комнаты. На сколько я понял задачу, необходимо изучить всю комнату.

[Syabro 81]

2 минуты назад, Zer0Galaxy сказал:

необходимо изучить всю комнату.

Все таки это невозможно сделать в 2д, если есть внутренние замкнутые пустоты

[Syabro 81]

Искуственные нейронные сети?

[eu_tomat 2 154]

1 час назад, Syabro сказал:

Отсканировать нормально комнату не выйдет по причине возможных замкнутых пространств в двумерном измерении. Внутрь он просто не попадет.

18 минут назад, Syabro сказал:

Все таки это невозможно сделать в 2д, если есть внутренние замкнутые пустоты

Исследовать несвязанные замкнутые полости ощупыванием границ не удастся также и в 3D. На то они и замкнутые и несвязанные. Но автору вопроса это вряд ли требуется, учитывая, что он планировал исследовать комнату непосредственно контактируя с её границами.