roboforum.ru

Если есть сильные в геометрии программеры \ математики, отзовитесь!

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

Но начнем мы попробуем конечно с простого - ограничимся выпуклыми многоугольниками. И будем с ними делать операции "объединить" и "вычесть", чтобы наносить на карту новые обнаруженные препятствия и убирать те препятствия, которых мы не обнаружили.

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

PS: Надо будет эту тему и про поиск пути перетащить в Алгоритмы вроде там ей место.

А для каких мозгов планируется решение задачи? Контроллер? ПК? Если ресурсов достаточно, то, может, удобнее будет с пожизненно выпуклыми треугольниками работать? А если мозг быстрый и памяти много, то, может, их закрашивать цветасто? Я чего-то совсем не в теме. А где можно поконкретней про цели-задачи, техническую базу и обоснование выбора (в смысле почему битовые карты не устраивают?) такого подхода прочитать?

SSG писал(а):А для каких мозгов планируется решение задачи? Контроллер? ПК? Если ресурсов достаточно, то, может, удобнее будет с пожизненно выпуклыми треугольниками работать? А если мозг быстрый и памяти много, то, может, их закрашивать цветасто? Я чего-то совсем не в теме. А где можно поконкретней про цели-задачи, техническую базу и обоснование выбора (в смысле почему битовые карты не устраивают?) такого подхода прочитать?

ПК, по возможности - КПК/ARM.

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

С треугольниками работать - так плодиться они начнут не по детски (пересечение 2 треугольников - до 6 угольника может быть, а значит это минимум сразу 3 треугольника) а когда путь ищешь - время работы пропорционально квадрату количества вершин, поэтому если наплодить треугольников - запаришься потом среди них путь искать.

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

А может можно как-нибудь средства OpenGL привлечь для расчетов?

SSG писал(а):А может можно как-нибудь средства OpenGL привлечь для расчетов?

А конкретней?

Добавлено спустя 18 часов 12 минут 3 секунды:
В общем пока следующие выводы:

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

2. Для невыпуклых многоугольников без самопересечений всё не так просто, однако есть библиотеки, например: http://www.cs.man.ac.uk/~toby/alan/software/

3. Обзор разных библиотек и алгоритмов для двоичных операций над многоугольниками: http://www.complex-a5.ru/polyboolean/comp.html

.

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

Или все ж считаем, что вся карта пуста и наносим на нее отрезки препятствий, удаляя те части уже нанесенных отрезков, которые попадают в "прострелянный" сенсором треугольник? Тогда все построение карты сведется к пересечению отрезков...

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

Или все ж считаем, что вся карта пуста и наносим на нее отрезки препятствий, удаляя те части уже нанесенных отрезков, которые попадают в "прострелянный" сенсором треугольник? Тогда все построение карты сведется к пересечению отрезков...

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

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

Добавлено спустя 7 часов 43 минуты 19 секунд:
На новогодние праздники уезжаю туда, где не будет интернета не теряйте, планирую появится 6-го

Всё, я вернулся

После прочтения обзора http://www.complex-a5.ru/polyboolean/comp.html становится ясно, что это не самый лучший вариант среди тех, кому можно верить (автор обзора является автором одной из рассматриваемых библиотек). Однако, учитывая, что другого обзора нет, а автор из соотечественников и защищал примененные алгоритмы на конференциях и в своей научной работе и предлагает как коммерческий вариант библиотеки, так и бесплатный для некоммерческого использования - можно попробовать ему поверить и применить его вариант библиотеки.

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

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

Добавлено спустя 6 минут 53 секунды:
Еще надо приземлить один вопрос - как храним различную информацию. Всего для информации о площадях у нас есть 3 базовых типа - непроходимая область, проходимая область и неразведанная область.

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

Кто что по этому поводу думает?

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

Strijar писал(а):Приобретение дальномера тоже меня подводит к мысли использовать векторную карту. Я в первом приближении решил так - "Кругом враги" Т.е. пока карты нет - вокруг, вплотную "стена", а дальномер эту стену отодвигает. Отрезок стены делится положением дальномера и отодвигается на величину его показаний. Потом для оптимального движения в карте можно подумать о применение пространственных "деревьев". Например BSP-Tree

Пространственных то вам зачем?
У вас вертолет?

Не. У нас дирижабль! Комнатный Есть такая задумка... на будущее

Вот. Я тоже вернулся

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

А дирижабль - это круто! Пепелац такой за тапками гонять...

Digit писал(а):тут мы где-то обсуждали, что если не отличать неисследованные зоны от исследованных, тогда робот не сможет планировать свой путь из одной комнаты в другую. Он вначале всегда будет утыкаться в стенку, а потом вдоль нее идти... Либо всегда будет идти разведанным маршрутом, даже если маршрут будет не оптимальным. Короче, не понятно, как подходить к процессу разведки территории интеллектуально.

А что непонятного то? Всё как у людей

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

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

Насчет анализа библиотек.
А как бы хоть примерно оценить количество точек и данных? Например, с работой на мегу и хранением в памяти на I2C большое количество точек нереально потянуть, а значит, возможно, лучшим решением будет метод GPC (особенно, если его реально оптимизировать под конкретное ядро).
В общем, я к тому, что надо бы хоть на глаз оценить количество точек для "средней" задачи. А библиотеки по возможности вообще сделать взаимозаменяемыми... (это утопия скорее всего )

Добавлено спустя 6 минут 47 секунд:

=DeaD= писал(а):

Digit писал(а):Короче, не понятно, как подходить к процессу разведки территории интеллектуально.

А что непонятного то? Всё как у людей

Не получается, как у людей! Т.к. человек помнит, что он где-то не ходил и там имеет смысл поискать, а робот знать этого не будет. И тогда у него будет только два режима:
1. Движение по уже разведанному пути
2. Тотальный поиск несоответствий карты и реального мира

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

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

Digit писал(а):Насчет анализа библиотек.
А как бы хоть примерно оценить количество точек и данных? Например, с работой на мегу и хранением в памяти на I2C большое количество точек нереально потянуть, а значит, возможно, лучшим решением будет метод GPC (особенно, если его реально оптимизировать под конкретное ядро).
В общем, я к тому, что надо бы хоть на глаз оценить количество точек для "средней" задачи. А библиотеки по возможности вообще сделать взаимозаменяемыми... (это утопия скорее всего )

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

Digit писал(а):Не получается, как у людей! Т.к. человек помнит, что он где-то не ходил и там имеет смысл поискать, а робот знать этого не будет. И тогда у него будет только два режима:
1. Движение по уже разведанному пути
2. Тотальный поиск несоответствий карты и реального мира

Неа

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

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

Digit писал(а):Если вводится понятие "неизведанная территория", то режимов побольше получаем:
1. Движение по уже разведанному пути
2. Анализ неразведанной территории
3. Тотальный поиск несоответствий на карте.
Причем сказать хозяину после п.3, что он не прав и дороги нет, вполне возможно

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