Пока не сделали ориентации по маякам предлагаю обсудить какие есть алогритмы обхода территории...
1. вдоль плинтуса
2. по восходящей спирали
3. метод тыка и разворот на произвольный угол
кто еще что знает, а то гуглить что-то не получается, наверно не правильно запрос строю
roboforum.ru
Технический форум по робототехнике.
Алгоритм - обход пылесосом территории
Re: Алгоритм - обход пылесосом территории
Если территория очень простая, то вариантов бесконечно много, самые быстрые (imho) спираль и змейка.
А для сколько-нибудь сложной обстановки карта по зарез нужна.
Если разбить все пространство 256x256 и записывать только был/небыл (1 бит) потребуется 8K памяти
При точности пространства 2см комната может быть размером 256*0.02= 5мx5м
Не все так просто: по карте-то можно будет ходить только если ошибка навигации накапливаться не будет. А если навигация без ошибки есть - можно реализовать и древо решений, обойдясь меньшей памятью. То есть прядя откуда-то мы имеем три направления движения: прямо, налево, направо. выбираем прямо, запоминаем выбор, переходим к следующей точке пытаемся идти прямо, не получается - идем налево, не получается - направо, не получается - возвращаемся в преддыдущую точку и выбираем иное направление движения. Если нужно, то возвращаемся в дереве на самый верх.
А для сколько-нибудь сложной обстановки карта по зарез нужна.
Если разбить все пространство 256x256 и записывать только был/небыл (1 бит) потребуется 8K памяти
При точности пространства 2см комната может быть размером 256*0.02= 5мx5м
Не все так просто: по карте-то можно будет ходить только если ошибка навигации накапливаться не будет. А если навигация без ошибки есть - можно реализовать и древо решений, обойдясь меньшей памятью. То есть прядя откуда-то мы имеем три направления движения: прямо, налево, направо. выбираем прямо, запоминаем выбор, переходим к следующей точке пытаемся идти прямо, не получается - идем налево, не получается - направо, не получается - возвращаемся в преддыдущую точку и выбираем иное направление движения. Если нужно, то возвращаемся в дереве на самый верх.
Последний раз редактировалось mandigit 09 мар 2008, 20:30, всего редактировалось 1 раз.
Re: Алгоритм - обход пылесосом территории
Я думаю если помещение без препятствий, то змейка между двумя стенами рулит. Потому как в этом случае следующий проход можно делать с некоторым перекрытием с предыдущим проходом, что значительно уберёт проблемы накапливаемой погрешности. И пофиг, что при подъезде к другой стене робот уже повернеться на 30 градусов и косо будет пылесосить, перекрывающиеся полосы компенсируют эту проблему. Ну это всё если конечно погрешность за 2 пробег от стены до стены и обратно не будет соизмерима с шириной убираемой полосы. А если будет - тогда все методы будут сравнимы со случайным блужданием.
Re: Алгоритм - обход пылесосом территории
а можно простенький рисоночек этой змейки с учетом стен? 
Re: Алгоритм - обход пылесосом территории
EdGull писал(а):а можно простенький рисоночек этой змейки с учетом стен?
Вот. Красное пятно - точка старта.
- Вложения
-
- zmeika.jpg (74.58 КиБ) Просмотров: 11185
Re: Алгоритм - обход пылесосом территории
вери-вери сенкую... 
Re: Алгоритм - обход пылесосом территории
А на основе чего робот умеет производить маневр? Что известно?
Если не ошибаюсь, робот умеет:
1. Определить препятствие по правому/левому борту
2. Повернуть на заданный угол относительно начального положения
3. Ехать, сохраняя прямолинейность движеня
в процессе движения идет накопление ошибки как по местоположению, так и по азимуту
получается, что алгоритм должен содержать элементы, нивелирующие накапливаемую ошибку
вариант
обходим территорию поворачивая на угол 170 град, до тех пор, пока расстояние движения от препятствия до препятствия не станет маленьким, тогда разворачиваемся на 90 град и снова так-же сканируем комнату
Если не ошибаюсь, робот умеет:
1. Определить препятствие по правому/левому борту
2. Повернуть на заданный угол относительно начального положения
3. Ехать, сохраняя прямолинейность движеня
в процессе движения идет накопление ошибки как по местоположению, так и по азимуту
получается, что алгоритм должен содержать элементы, нивелирующие накапливаемую ошибку
вариант
обходим территорию поворачивая на угол 170 град, до тех пор, пока расстояние движения от препятствия до препятствия не станет маленьким, тогда разворачиваемся на 90 град и снова так-же сканируем комнату
- Вложения
-
- alg1.gif (8.86 КиБ) Просмотров: 11747
Re: Алгоритм - обход пылесосом территории
mandigit писал(а):обходим территорию поворачивая на угол 170 град
То есть возвращаясь назад под углом 10 град? Но тут тогда какая проблема - ширина убираемой полосы не более 20см, а значит при расстоянии от стены до стены 3м (вполне нормальное расстояние для квартир) мы будем в стороне от исходной позиции на 30см, так что меньше надо угол брать, к тому же чтобы почти всегда перекрытие получалось. Думается максимум на 5 градусов можно отклоняться.
Re: Алгоритм - обход пылесосом территории
Ну 10 градусов - это так, для примера.
Как сама идея-то живая?
Как сама идея-то живая?
Re: Алгоритм - обход пылесосом территории
Есть патент на алгоритм обхода для румбы. Можно там посмотреть.
Re: Алгоритм - обход пылесосом территории
mandigit писал(а):Ну 10 градусов - это так, для примера.
Как сама идея-то живая?
Идея то живая, только от моего предложения она практически не отличается, точнее отличается, но в худшую сторону
Потому как дополнительной точности не создает, а перекрывает области хуже.Re: Алгоритм - обход пылесосом территории
Отличия есть:
- не требуется обеспечить точку старта в углу комнаты
- не требуется обеспечить начальное движение параллельно стене справа
то есть предложенный алгоритм является самостоятельным!
- не требуется обеспечить точку старта в углу комнаты
- не требуется обеспечить начальное движение параллельно стене справа
то есть предложенный алгоритм является самостоятельным!
Re: Алгоритм - обход пылесосом территории
А что у вас в комнатах нету мебели , поставьте туда 2 табуретки и посмотрите что будет.
Алгоритм лучше отладить на симуляторе.
, поставьте туда 2 табуретки и посмотрите что будет.Алгоритм лучше отладить на симуляторе.
Re: Алгоритм - обход пылесосом территории
mandigit писал(а):Отличия есть:
- не требуется обеспечить точку старта в углу комнаты
- не требуется обеспечить начальное движение параллельно стене справа
то есть предложенный алгоритм является самостоятельным!
1. Если старт из любой точки - почему он большие области не оставит без внимания и когда останавливаться?
2. Как быть с обычно самыми грязными участками рядом со стенами? У вас их игнорировать будет робот при езде под углом?
Re: Алгоритм - обход пылесосом территории
Алгоритм лучше отладить на симуляторе.
а какие нынче модно симуляторы юзать в которых можно рисовать свои стены?