roboforum.ru

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

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

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

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

Сообщение Виталий » 20 июн 2008, 23:39

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

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

Сообщение =DeaD= » 21 июн 2008, 08:45

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

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

Сообщение Vovan » 21 июн 2008, 11:31

Ну дак и предложил бы, нам нецивилизованным, реальное решение. Только почему-то мир цивилизованных создателей пылесосов расколот, если не сказать раздроблен и фиг знает кто из этих осколков цивилизованный. В одних цивилизованных фирмах алгоритм случайного блуждания, в других несколько программируемых траекторий, в третьих ограничительные маяки, в четвёртых операционная система и карта... можно продолжать и продолжать... Дак где же он ентот пресловутый цивилизованный мир?
_________
Sincerely,
Vovan
Аватара пользователя
Vovan
 
Сообщения: 3340
Зарегистрирован: 05 окт 2005, 12:03
Откуда: Литва
прог. языки: asm

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

Сообщение EdGull » 21 июн 2008, 20:02

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

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

Сообщение =DeaD= » 21 июн 2008, 22:42

Да везде он этот цивилизованный мир, и нигде алгоритмы с датчиками никто не смешивает :) нервничать то к чему?

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

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

Сообщение Vovan » 22 июн 2008, 01:22

Ничего я заводить не буду, потому что уже придумал (а точнее подсмотрел) вариант безо всяких видеокамер решается.
А насчёт цив. мира (от Dead): масло маслянное - достойный ответ :bad: . Ввел понятие - отвечай за него! А иначе лучше не вводил бы...
Ограничительные маяки - ИК стены - это разве не ясно? Какая нафик виртуальность? Мождь и ёмкое словечко, но не катит, потому что вирт. есть вирт. (см. словарь, википед., и т.д.)
А теперь по теме: по двум переменным, алгоритм построить тяжело, если не сказать больше - невозможно (ИМХО)! Поэтому (блин! неужто непонятно!?) предлагаю ввести третью и этой третьей является та самая фича которую и называют здесь "датчик пыли". И тему заводить, пока, нет смысла! Потому что тема "алгоритм..." будет топтаться на месте (это и к бабке не ходи!) пока не перейдём в следующий этап. Вот тогда (!), возможно, и появится новая тема.
А теперь повторюсь: тема исчерпана, бесполезняк=))
Одни буквы беспонтовые и сверкания своей исключительностью :ROFL: , больше ничего.
_________
Sincerely,
Vovan
Аватара пользователя
Vovan
 
Сообщения: 3340
Зарегистрирован: 05 окт 2005, 12:03
Откуда: Литва
прог. языки: asm

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

Сообщение EdGull » 22 июн 2008, 02:23

потому что уже придумал (а точнее подсмотрел) вариант безо всяких видеокамер решается.

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

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

Сообщение =DeaD= » 22 июн 2008, 10:10

Vovan писал(а):Ничего я заводить не буду, потому что уже придумал (а точнее подсмотрел) вариант безо всяких видеокамер решается.
А насчёт цив. мира (от Dead): масло маслянное - достойный ответ :bad: . Ввел понятие - отвечай за него! А иначе лучше не вводил бы...

Вас сейчас разорвет наверное, откуда столько нервов? :) я сказал что алгоритмы это одно, а датчики это другое. За эти понятия я готов отвечать до конца, а то что вы там себе придумали - сами себе и отвечайте.

Vovan писал(а):Ограничительные маяки - ИК стены - это разве не ясно? Какая нафик виртуальность? Мождь и ёмкое словечко, но не катит, потому что вирт. есть вирт. (см. словарь, википед., и т.д.)

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

Vovan писал(а):А теперь по теме: по двум переменным, алгоритм построить тяжело, если не сказать больше - невозможно (ИМХО)! Поэтому (блин! неужто непонятно!?) предлагаю ввести третью и этой третьей является та самая фича которую и называют здесь "датчик пыли". И тему заводить, пока, нет смысла! Потому что тема "алгоритм..." будет топтаться на месте (это и к бабке не ходи!) пока не перейдём в следующий этап. Вот тогда (!), возможно, и появится новая тема.

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

Vovan писал(а):Одни буквы беспонтовые и сверкания своей исключительностью :ROFL: , больше ничего.

Если вам нечего сказать больше - это не значит, что другим нечего сказать. Или у вас что-то горит и вам надо куда-то спешить и вы требуете, чтобы вам тут прямо и быстро дали ответ?

PS: Вообще мы еще тут не обсуждали вторую интересную часть этой темы :), допустим мы научились получать свои глобальные координаты (ну мало ли каким образом, хоть DGPS подешевеет в рамках небольших помещений), - как в этом случае проложить маршрут при известной карте, чтобы за минимальное время пропылесосить сложное помещение? Тема кстати для серьезных научных работ и не факт, что она не NP-полная.

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

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

Сообщение omlin » 22 июн 2008, 18:59

В пятницу накатал-таки программулину (первую часть), а вот времени выложить результаты уже не осталось
=DeaD= кстати был прав, за полчаса я не справился :( Ибо тригонометрию забыл, пришлось вспоминать по википедии...
Да и кроме того, впереди еще вторая часть...

Дак вот!
В симуляции я сделал следующим образом:
робот имеет два основных сенсора:
1) бампер спереди
2) датчик стены

Кроме того, робот имеет:
1) энкодер
2) некий абстрактный пока что достоверный датчик направления. это либо компас, либо какая то комбинация энкодеров - на сегодняшний день прока неважно, ограничимся лишь тем, что направление пока что определяется на 100% верно

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

кроме перечисленных датчиков робот более никак не получает информацию об окружающем мире

таким образом робот построил следующую карту:

simulation_first_attempt.jpg
результат работы программы


на реальной карте:
зеленым обозначаются пропылесосенные участки
красное - маяк, выставляемый роботом при первом касании стены
черное - стены
ну и изображение робота - что-то непонятное с коричневыми углами :)

на карте робота:
красным обозначены участки, построенные в процессе "подруливания" к стене после размыкания датчика стены.
черным - участки, построенные в результате движения вдоль стен.

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

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

вот собственно.
вопрос вот в чем:
у кого-нибудь есть идеи, как конкретно смыкать линии? :)
я сам над этим буду думать, но вдруг уже кто-то решал эту проблему

кстати, вот "программулина":
testcleaner.zip
симулятор
(223.65 КиБ) Скачиваний: 51

в архиве exe-шник и простенькая карта, такая же как в примере выше
вроде бы, должно у всех запускаться... (надеюсь)

наверное, проще и более реалистично было бы написать сразу для Robotics Studio, но дельфийский вариант гораздо доступнее, ведь не у всех установлен фреймворк - я так думаю:) у меня например дома не установлен...

второй этап, кстати, еще интереснее... мы уже тут с Виталием ковыряли его особенности, ну время придет - выложу :)

p.s.
=DeaD= писал(а):Добавлено спустя 1 час 55 минут 54 секунды:Кстати, о птичках - пока мы тут пылесосим, люди урожай убирают это я про подешевевший DGPS, его уже сейчас в некоторых областях используют: m http://www.agroit.com.ua/main/146/

а вот это вот оооочень интересненько!! :)

Добавлено спустя 11 минут 3 секунды:
да, ошибочку с моей идеальной несмыкаемостью обнаружил.
неправильно считается расстояние при перемещении под непрямым углом (там делается просто +1 к пройденному расстоянию, а нужно учитывать текущий угол поворота).

на идеально квадратно-прямоугольных картах все сходится тютелька в тютельку

но в принципе, это не особо важно, как я уже говорил. все равно погрешности будут, и нужно смыкать...
жду ваших мыслей, уважаемые ))
Мой блог "Роботы и робототехника": http://insiderobot.blogspot.com
omlin
 
Сообщения: 39
Зарегистрирован: 31 окт 2007, 14:25
Откуда: Кострома

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

Сообщение =DeaD= » 22 июн 2008, 20:49

Перечитал 3 раза сообщение, так и не понял, что за задача такая "смыкать линии" ?

Можно подробнее о задаче, которую надо решить, так сказать, для танкистов :)

PS: Какие погрешности ввели в программу, чтобы было похоже на реальную ситуацию?

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

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

Сообщение Виталий » 23 июн 2008, 00:31

=DeaD= запусти программу и увидишь что смыкать надо =)

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

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

Сообщение =DeaD= » 23 июн 2008, 08:57

Понял примерно в чем вопрос :) хотя еле дождался :) короче у вас оно начинает карту заново рисовать по второму кругу - так?

В общем для того чтобы смыкать линии надо сделать очень простой ход:
1. При запоминании карты запоминать не только линию, но и с какой стороны от неё мы прошли;
2. При прохождении смотреть, если у нас получается две такие линии одинаковой направленности с расстоянием между ними меньше ширины робота, значит надо их сомкнуть.

Если совсем грубо и считаем, что на карте нет объектов шириной меньше робота, тогда направленность можно игнорировать.

Добавлено спустя 20 минут 10 секунд:
А про зависает - это да, ппц :) но я думаю это связано со смыканием. По идее как только линия сомкнулась надо определить по его направлению, внешний это контур был или внутренний, если внутренний, тогда идем в любую сторону от него, пока не найдем еще что-нибудь, в надежде, что внешний контур всё-таки существует :)

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

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

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

Сообщение omlin » 23 июн 2008, 09:31

а у меня вроде не зависает слева от кругляшка...
покажите пальцем где ставить (на скриншоте)?
я, видите ли, подозреваю из-за чего он может виснуть...

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

Код: Выделить всёРазвернуть
  stage1:array [1..3, 1..5] of byte =
           // 1  2  3  4  5
(*бампер*) (( 2, 2, 5, 5, 5),
(*стенка*)  ( 3, 3, 3, 3, 3),
(*размык*)  ( 1, 2, 4, 4, 5)
           );


датчики:
бампер - все пространство строго впереди робота
стена - все пространство строго слева от робота
размык - размыкание датчика стены

состояния:
1 - начальный этап свободного поиска, длится до тех пор, пока не коснемся стены бампером или датчиком стены
2 - разворот до тех пор, пока не коснемся стены датчиком стены
3 - движемся вдоль стены до тех пор, пока не произойдет размыкание
4 - состояние "подруливания" к стене, после размыкания датчика стены
5 - разворот после срабатывания бампера, до тех пор, пока не коснемся стены датчиком стены

на пересечении - номер состояния, в которое перейдет система, в случае задействования того или иного датчика
датчики имеют приоритет.
если одновременно будут бампер и стена, то программа увидит только бампер.
Мой блог "Роботы и робототехника": http://insiderobot.blogspot.com
omlin
 
Сообщения: 39
Зарегистрирован: 31 окт 2007, 14:25
Откуда: Кострома

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

Сообщение =DeaD= » 23 июн 2008, 09:36

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

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

Сообщение omlin » 23 июн 2008, 10:33

а у меня все ок.... уже везде ставил где можно...
см. скриншот:
stolik.gif
столик в гостиной
stolik.gif (5.79 КиБ) Просмотров: 7071

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

по идее, конечно, нужно определять, является ли контур внешним или внутренним, и если он внешний, то нужно после его обхода при очередном отрыве от стены просто переходить в состояние 1 вместо 4.
но это не проблема :)

проблема - несмыкаемость...

=DeaD= писал(а):2. При прохождении смотреть, если у нас получается две такие линии одинаковой направленности с расстоянием между ними меньше ширины робота, значит надо их сомкнуть.

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

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


как действовать в этом случае?

(при этом, робот уже гарантированно обнаружит, что он полностью проехал помещение, и не просто по направлению, а по выбрасываемому им красному маяку...)


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

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

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

у кого-нибудь есть идеи, как сделать это более красиво? :)
Мой блог "Роботы и робототехника": http://insiderobot.blogspot.com
omlin
 
Сообщения: 39
Зарегистрирован: 31 окт 2007, 14:25
Откуда: Кострома

Пред.След.

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

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

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