roboforum.ru

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

Алгоритм - обход пылесосом территории

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

Алгоритм - обход пылесосом территории

Сообщение EdGull » 09 мар 2008, 15:24

Пока не сделали ориентации по маякам предлагаю обсудить какие есть алогритмы обхода территории...
1. вдоль плинтуса
2. по восходящей спирали
3. метод тыка и разворот на произвольный угол

кто еще что знает, а то гуглить что-то не получается, наверно не правильно запрос строю
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

Re: Алгоритм - обход пылесосом территории

Сообщение mandigit » 09 мар 2008, 19:40

Если территория очень простая, то вариантов бесконечно много, самые быстрые (imho) спираль и змейка.
А для сколько-нибудь сложной обстановки карта по зарез нужна.
Если разбить все пространство 256x256 и записывать только был/небыл (1 бит) потребуется 8K памяти
При точности пространства 2см комната может быть размером 256*0.02= 5мx5м

Не все так просто: по карте-то можно будет ходить только если ошибка навигации накапливаться не будет. А если навигация без ошибки есть - можно реализовать и древо решений, обойдясь меньшей памятью. То есть прядя откуда-то мы имеем три направления движения: прямо, налево, направо. выбираем прямо, запоминаем выбор, переходим к следующей точке пытаемся идти прямо, не получается - идем налево, не получается - направо, не получается - возвращаемся в преддыдущую точку и выбираем иное направление движения. Если нужно, то возвращаемся в дереве на самый верх.
Последний раз редактировалось mandigit 09 мар 2008, 20:30, всего редактировалось 1 раз.
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: Алгоритм - обход пылесосом территории

Сообщение =DeaD= » 09 мар 2008, 20:03

Я думаю если помещение без препятствий, то змейка между двумя стенами рулит. Потому как в этом случае следующий проход можно делать с некоторым перекрытием с предыдущим проходом, что значительно уберёт проблемы накапливаемой погрешности. И пофиг, что при подъезде к другой стене робот уже повернеться на 30 градусов и косо будет пылесосить, перекрывающиеся полосы компенсируют эту проблему. Ну это всё если конечно погрешность за 2 пробег от стены до стены и обратно не будет соизмерима с шириной убираемой полосы. А если будет - тогда все методы будут сравнимы со случайным блужданием.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм - обход пылесосом территории

Сообщение EdGull » 09 мар 2008, 20:45

а можно простенький рисоночек этой змейки с учетом стен? :oops:
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

Re: Алгоритм - обход пылесосом территории

Сообщение =DeaD= » 09 мар 2008, 21:14

EdGull писал(а):а можно простенький рисоночек этой змейки с учетом стен? :oops:

Вот. Красное пятно - точка старта.
Вложения
zmeika.jpg
zmeika.jpg (74.58 КиБ) Просмотров: 10161
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм - обход пылесосом территории

Сообщение EdGull » 09 мар 2008, 21:33

вери-вери сенкую... :friends:
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

Re: Алгоритм - обход пылесосом территории

Сообщение mandigit » 09 мар 2008, 21:50

А на основе чего робот умеет производить маневр? Что известно?

Если не ошибаюсь, робот умеет:
1. Определить препятствие по правому/левому борту
2. Повернуть на заданный угол относительно начального положения
3. Ехать, сохраняя прямолинейность движеня
в процессе движения идет накопление ошибки как по местоположению, так и по азимуту

получается, что алгоритм должен содержать элементы, нивелирующие накапливаемую ошибку
вариант
обходим территорию поворачивая на угол 170 град, до тех пор, пока расстояние движения от препятствия до препятствия не станет маленьким, тогда разворачиваемся на 90 град и снова так-же сканируем комнату
Вложения
alg1.gif
alg1.gif (8.86 КиБ) Просмотров: 10727
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: Алгоритм - обход пылесосом территории

Сообщение =DeaD= » 09 мар 2008, 22:51

mandigit писал(а):обходим территорию поворачивая на угол 170 град

То есть возвращаясь назад под углом 10 град? Но тут тогда какая проблема - ширина убираемой полосы не более 20см, а значит при расстоянии от стены до стены 3м (вполне нормальное расстояние для квартир) мы будем в стороне от исходной позиции на 30см, так что меньше надо угол брать, к тому же чтобы почти всегда перекрытие получалось. Думается максимум на 5 градусов можно отклоняться.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм - обход пылесосом территории

Сообщение mandigit » 10 мар 2008, 01:53

Ну 10 градусов - это так, для примера.
Как сама идея-то живая?
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: Алгоритм - обход пылесосом территории

Сообщение Виталий » 10 мар 2008, 23:49

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

Re: Алгоритм - обход пылесосом территории

Сообщение =DeaD= » 11 мар 2008, 00:19

mandigit писал(а):Ну 10 градусов - это так, для примера.
Как сама идея-то живая?

Идея то живая, только от моего предложения она практически не отличается, точнее отличается, но в худшую сторону :) Потому как дополнительной точности не создает, а перекрывает области хуже.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм - обход пылесосом территории

Сообщение mandigit » 11 мар 2008, 10:44

Отличия есть:
- не требуется обеспечить точку старта в углу комнаты
- не требуется обеспечить начальное движение параллельно стене справа

то есть предложенный алгоритм является самостоятельным!
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: Алгоритм - обход пылесосом территории

Сообщение Master » 11 мар 2008, 11:42

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

Re: Алгоритм - обход пылесосом территории

Сообщение =DeaD= » 11 мар 2008, 17:14

mandigit писал(а):Отличия есть:
- не требуется обеспечить точку старта в углу комнаты
- не требуется обеспечить начальное движение параллельно стене справа

то есть предложенный алгоритм является самостоятельным!

1. Если старт из любой точки - почему он большие области не оставит без внимания и когда останавливаться?
2. Как быть с обычно самыми грязными участками рядом со стенами? У вас их игнорировать будет робот при езде под углом?
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм - обход пылесосом территории

Сообщение EdGull » 11 мар 2008, 17:17

Алгоритм лучше отладить на симуляторе.

а какие нынче модно симуляторы юзать в которых можно рисовать свои стены?
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

След.

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

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

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