Софт
Программное обеспечение
RoboMap
Программа для изучения работы алгоритмов поиска пути и обхода препятствий

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

Программа RoboMap позволяет создать квадратную карту размером от 16х16 до (с версии 1.0.0.6) 256х256 клеток-ячеек.

Клетки карты могут иметь следующие значения:

Разница между стеной и предметом чисто визуальная, обрабатываются они одинаково: обходятся по кратчайшему пути. созданную карту можно сохранить в файл формата csv, текстовая таблица, значения разделены запятыми. Можно открыть в Excel или другой пограмме, поддерживающей этот формат данных.

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

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

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

К программе приложены образцы скриптов и карт. Карты на 64 и 96 клеток специально сделаны так, чобы демонстрировать разницу в работе алгоритмов поиска пути по 4 и по 8 клеткам: результаты очень показательые.
Софт
Программное обеспечение
RoboMap
Программа для изучения работы алгоритмов поиска пути и обхода препятствий

Поле Градиента расстояния создает очень простую и ясную "указующую" картину, пройти по которой можно "с завязанными глазами". Однако на достаточно сложных картах вместо тонкой ниточки пути образуется тропка, по которой можно пройти или прямо, или зигзагами. Или справа обойти, или слева. Реализовать эти варианты можно с помощью описания правил поведения бота на карте. Для этого достаточно вписать в файл описания бота некоторое количество правил.

Правила представляют собой список рекомендаций: как поступать в случае появления той или иной комбинации направлений на поле градиента расстояний.

Каждую клетку окружает 8 полей. Бот получает список значений этих клеток, нормированных по значению градиента в той клетке, в которой стоит бот. Полученная строка с перечнем направлений, в которых градиент сильнее всего. Если это одно-единственное направление, то боту и думать нечего - иди куда зовут. Например, получен список вида "1Т". Рекомендация для этого случая будет соответствующее: "#T".
Соответствующее правило для бота будет выглядеть так:
rule (#T:1T)
Но чаще бывает, что поле градиента выражено нечетко и есть варианты в виде нескольких равно оптимальных направлений. Например, вверх, вверх-вправо и вверх-влево. Бот в этом случае получает строку 1T,1LT,1RT. Можно, конечно, решить, что всегда идти "по центру" и прописать в правилах строку:
rule (#T:1T,1LT,1RT)
и бот будет в таком случае всегда идти вверх. Однако это не всегда может оказаться лучшим выбором. Чтобы реализовать выбор, если он возможен и желателен, можно в правилах перечислить варианты для таких случаев. Это будет выглядеть так:
rule (#T,#LT,#RT:1T,1LT,1RT)
Получив такую кучу рекомендаций, бот выберет одно из предложенных направлений случайным образом. Прокладываемая по таким правилам трасса будет иногда отклоняться в стороны, но в пределах правильного пути. Но и это еще не все! :)

В алгоритме нет никаких ограничений на количество одинаковых рекомендаций в одном правиле. Если программист сочтет, что даже при равном весе вариантов предпочтительнее все же какое-то одно направление, к примеру, вверх, то можно написать следующее правило:
rule (#T,#T,#LT,#RT:1T,1LT,1RT)
Бот будет послушно выбирать из всех предложе6нных ему рекомендаций, в результате чего выбор "вверх" будет производиться вдвое чаще, чем другие варианты. Если вариант "вверх" прописать трижды - то втрое чаще... И так далее.
Можно дать боту возможность выбора даже там, где он не нужен. Тогда получим "нелогичного бота".
Бот будет ближе к человеку... :)

Кардинально повлиять на поиск пути можно также и с помощью команды CheckPoint, в параметре которой перечисляются все направления, информация о состоянии которых будет обрабатывать правилами бота. Так, обрабатывая все восемь направления, бот должен объявить это строкой
CheckPoint (T,LT,L,LB,B,RB,R,RT)
и эта команда должна быть записана в файле описания бота перед списком правил. Разумеется, заявив о восьми обрабатываемых направлениях, надо позаботиться о том, чтобы в списке правил были предусмотрены обработчики всех этих направлений и комбинаций направлений. В противном случае деятельность бота ограничится заполнением лога сообщениями об ошибках.
Классический "четырехклеточный бот" заявляется командой
CheckPoint (T,L,B,R)
и список правил этого бота может ограничиться всего восемью правилами:

bot простой 4-клеточный
    CheckPoint (T,L,B,R)
    Rule (#T:1T)
    Rule (#L:1L)
    Rule (#B:1B)
    Rule (#R:1R)
  Rule (#T,#L:1T,1L)
  Rule (#L,#B:1L,1B)
  Rule (#R,#T:1R,1T)
  Rule (#B,#R:1B,1R)
endbot
Впрочем, иногда возможны дикие варианты комбинаций фактов типа 1T,1B, которые тоже надо предусмотреть...
Железный Феликс, Арсеньев А. А., 2008 г.

Робот - статистик