Самодельный робот |
Статьи о роботахАлгоритм поиска пути для роботов Выбор и описание алгоритма поиска пути, подходящего для использования при ориентировании мобильных роботов по заранее заданной карте местности Автор: Андрей Маркеев Язык для описания роботов RoboML Стандартизация представления данных является важным моментом любой области знаний. RoboML - язык, который решает эту задачу в области робототехники. Автор: Андрей Маркеев XML-спецификация языка описания роботов, снабженная подробными русскими комментариями. Детальное ее описание - в следующей статье о RoboML. Автор: Андрей Маркеев Рассматривается использование робота, сделанного на основе персонального компьютера, в охранных системах. Автор: Андрей Маркеев Робот и искусственный интеллект Подход к использованию технологий искусственного интеллекта в системе управления роботов. Автор: Андрей Маркеев Общая идея. Краткое описание текущего положения дел в области робототехники, предпосылок для создания описываемого робота, потенциальных возможностей применения и т.д. Автор: Андрей Маркеев |
|
|||||||||||||||||||||||||
вернуться к списку статейАлгоритм поиска пути для роботовАвтор: Маркеев Андрей Перепечатка материалов статьи Речь в этой статье пойдет о подходе к реализации поиска пути по заранее заданной карте - для мобильных роботов, создаваемых на базе компьютера или ноутбука. Собственный самодельный робот автора имеет некоторые особенности, связанные с его ориентированием. В частности, карта для робота задается в виде обычного графического файла формата BMP, черным на ней помечены непроходимые препятствия, красным - «опасные» участки, где следует двигаться с повышенной осторожностью (читать - двигаться медленнее, чем обычно). Обычно карта такого рода получается с помощью сканирования плана квартиры или любого другого помещения, и дополнения этого плана красными пометками в местах, где открываются двери, могут располагаться стулья, столы, или - где часто ходят люди. Вопрос о текущем положении робота, корректировка текущего положения - решается с помощью датчиков обратной связи, а также системы ориентирования по ИК-маякам. Эти моменты подробно описаны на авторском сайте http://robot.paccbet.ru. Что касается одной из основных функций робота - движение в заранее заданную точку согласно известного плана помещения - она реализуется полностью программно. Рассмотрим, какие трудности и тонкости ожидают нас при программировании этой функции:
Прежде всего, рассмотрим существующие алгоритмы поиска пути. На первый взгляд, алгоритмы поиска пути в современных стратегических играх реального времени - именно то, что нам нужно! Решена проблема собственно поиска пути, алгоритм оптимален с точки зрения быстродействия (и даже переписан на ассемблер!), также присутствует постоптимизация - "сокращение" обходов. Однако многих перечисленных выше проблем такие алгоритмы не решают, а следовательно, могут служить лишь основой для подхода к программированию поиска пути в робототехнике. Примечание: Как пример, автор рассматривал код стратегической игры Warcraft 2000.
В данной ситуации автору при разработке собственного робота очень помогла задача, которую он решал, будучи еще студентом, на занятиях по дисциплине «Искусственный интеллект».
Такая задача уже гораздо более похожа на ту, которую предстоит решать при реализации поиска пути для робота. Учитывается размер быка, и есть «опасные» зоны, которые необходимо по возможности обходить. Остаются, конечно, нерешенные проблемы (пп. 3-5), однако они не критичны. Соизмерение масштаба карты и управления двигателями должен взять на себя драйвер приводов. Наименьшее количество поворотов достигается «срезанием» пути, алгоритм которого можно позаимствовать из компьютерных игр. Одна из возможных реализаций: между каждыми двумя точками итогового пути проводится линия, и проверяется, не встречает ли эта линия препятствий на карте. Плавность поворотов достигается путем интерполяции полученной линии в местах резких поворотов стандартными математическими методами. Итак, рассмотрим решение задачи «Быки и коровы». Корова в принципе стоит на месте, и с ней мы ничего сделать не можем. А а вот бык двигается вперед, опираясь на следующую информацию:
Дальше можно поступить, как поступают разработчики логических игр (шахматы, крестики-нолики и т.д.). А именно, назначить каждому правилу определенный «вес», затем путем сложения этих весов получается общий вес конкретной позиции быка. Из всех возможных вариантов движения (вперед, назад, влево, вправо, по диагонали) - выбирается тот, вес которого наилучший. Приступим к реализации. Для начала, определим, какие переменные и функции мы должны создать для того, чтобы следовать указанным правилам:
Создадим объект TBull (бык), его определение будет иметь следующий вид: TBull=object cowx,cowy:integer; top,left:integer; width,height:integer; lifes:shortint; memory:array [0..FieldHeight-1,0..FieldWidth-1]of byte; bestdistance:integer; distchange:integer; stepcount:integer; sbt:longint; taran:boolean; procedure reset; procedure go(x,y:integer); procedure setcow(x,y:integer); procedure step; function calcdistance(x,y:integer):integer; function calcfloor(x,y:integer;var front:integer):integer; function calcrepeat(x,y:integer):integer; end;
Опишу неупомянутые до сих пор переменные: Остановимся подробнее на вспомогательных функциях, учавствующих в поиске пути. Первым делом - приведу код функции calcdistance, которая вычисляет текущее расстояние между быком и коровой. Из школьного курса математики известно, что для вычисления расстояния между двумя точками, нужно взять корень от суммы квадратов разностей координат. Функция просто реализует эти вычисления: function TBull.calcdistance(x,y:integer):integer; begin calcdistance:=round(566 - sqrt(sqr(x-cowx) + sqr(y-cowy))); end; Еще одна вспомогательная функция, которая наглядно показывает, как отрабатывается размер робота, а также принципы обработки BMP-изображения - calcfloor. function TBull.calcfloor(x,y:integer;var front:integer):integer; var i,j:integer; t:array[0..2]of byte; f:byte; begin f:=0; for i:=0 to 2 do t[i]:=0; for i:=x-GodCowWidth div 2 to x+GodCowWidth div 2-1 do for j:=y-GodCowHeight div 2 to y+GodCowHeight div 2-1 do case (Form1.imgMap.Canvas.Pixels[i,j]) of clRed:inc(t[1]); clBlack:inc(t[2]); else inc(t[0]); end; if (t[0]>t[1])and(t[0]>t[2]) then f:=0; if (t[1]>t[0])and(t[1]>t[2]) then f:=1; if (t[2]>t[1])and(t[2]>t[0]) then f:=2; // front - процент вредных примесей в текущей подстилке front:=round((GodCowWidth*GodCowHeight-t[f])/(GodCowWidth*GodCowHeight)*100); calcfloor:=f; end; Отработка размера быка всегда сопровождается циклической обработкой следующего вида: for i:=x-GodCowWidth div 2 to x+GodCowWidth div 2-1 do for j:=y-GodCowHeight div 2 to y+GodCowHeight div 2-1 do Обратите внимание, координаты x и y считаются координатами центра быка. GodCowWidth и GodCowHeight - это константы, равные ширине и высоте быка в пикселах. В случае робота, нужно будет обмерить его максимальные значения для ширины и длины, соизмерить с масштабом карты, и внести в настройки программы управления робота. Причем, для упрощения, и если робот имеет более-менее круглую или квадратную форму, желательно, чтобы в программе он принимался за квадрат. Иначе - если робот сильно вытянут - алгоритм придется усложнять, вводя понятие текущего угла поворота и пересчитывать форму при каждом изменении этого угла. Наконец, перейдем к рассмотрению кода основной процедуры, реализующей алгоритм поиска пути для быка. procedure TBull.step; var i,j:integer; // переменные цикла t, // вычисляемый общий показатель позиции ("вес") p, // (pain) повреждение, которое получит бык d, // (distance) вычисляемая дистанция front, // вычисляемое количество примесей в подстилке my_f, // (my_floor) на какой подстилке жук находится в данный момент my_d // (my_distance) текущее расстояние до коровы :integer; best:record // лучшая из найденных позиций t,x,y,pain:integer; end; Первым делом - быстрая проверка, не нашли ли мы уже добычу (корову). if (abs(cowx-(left+GodCowWidth div 2))<=GodCowWidth) and (abs(cowy-(top+GodCowHeight div 2))<=GodCowHeight) then exit; Далее инициализируем переменные текущего состояния. Лучшей позиции для перемещения пока не найдено, пока что присваиваем ей отрицательное значение. best.t:=-maxint; my_f:=calcfloor(left+GodCowWidth div 2,top+GodCowHeight div 2,front); my_d:=calcdistance(left+GodCowWidth div 2,top+GodCowHeight div 2);
Далее - основной цикл.
Как Вы помните, жук имеет размер 8x8 пикселов, а его координаты - x и y, расположены в центре этого квадрата 8х8.
Для небольшого упрощения задачи, мы просматриваем все точки внутри быка, и находим из них самую лучшую.
Таким образом, перемещение осуществляется быстрее, чем если бы мы просматривали квадратик в 3х3 пиксела, и одновременно гарантируется, что жук не проскочит узкие щели на карте (благодаря тому, что известен размер жука).
for i := left to left+GodCowWidth do for j := top to top+GodCowHeight do if (i > GodCowWidth div 2) and (i < FieldWidth-GodCowWidth div 2-1) and (j > GodCowHeight div 2) and (j < FieldHeight-GodCowHeight div 2-1) then begin Вычисляем характеристики и «вес» для данной точки: d:=calcdistance(i,j); t:=round(d*2*(sbt/200+1)); p:=calcfloor(i,j,front); if (p=0)and(my_f<>0) then if (d-my_d<4) then t:=t-1000 else t:=t-100; if p=my_f then p:=0; if front>45 then t:=t-100; t:=t+(2-p)*1000; t:=t+calcrepeat(i,j); Отдельно обрабатывается таран: если в данный момент жук находится в состоянии тарана, и при этом разница между дистанцией до коровы в данной точке, и лучшей дистанцией, которую достигал жук, минимальна (не превышает 10 пикселов), то вес текущей позиции увеличивается, при этом компенсируется операция t:=t+(2-p)*1000 из предыдущего фрагмента кода, которая значительно уменьшает вес тех позиций, которые предполагают переход на другую подстилку. if (taran)and(bestdistance-d<=10) then t:=t+2000*(p+1); Если позиция оказалась наилучшей, запомним ее характеристики. if t>best.t then begin best.t:=t; best.x:=i; best.y:=j; best.pain:=p; end;
На этом основной цикл завершен, осталось собственно совершить переход, а также реализовать дополнительную логику тарана. Ведь на текущий момент, мы таран обработали, но при каких условиях жук переходит в состояние тарана, и как это делает - пока не указали.
end; // окончание основного цикла if best.t<>-maxint then begin if not taran then inc(sbt); // если мы не находимся в состоянии тарана - увеличим нетерпение быка inc(stepcount); // увеличиваем общее число шагов i:=left+GodCowWidth div 2; j:=top+GodCowHeight div 2; distchange:=calcdistance(best.x,best.y)-my_d; // определяем, насколько изменилась дистанция до коровы go(best.x,best.y); // собственно, переходим на новую позицию Нужно ранить жука, в случае, если он перешел на другую подстилку. В случае реализации поиска пути для робота, сам факт ранения, конечно, не потребуется. Однако кроме просто отсчета жизней, данный фрагмент реализует сброс состояния «таран». Иными словами, жук идет на таран только до первого перехода, а затем снова переходит в обычное состояние поиска. if best.pain>0 then begin dec(lifes,best.pain); TimerEnabled:=false; Application.MessageBox(PChar('Ай, больно! Осталось жизней: '+inttostr(lifes)),'Божий бык',0); TimerEnabled:=true; taran:=false; end; Вычисляем необходимость тарана. Если идем на таран - память посещений клеток очищается. if not taran and(sbt>500) then begin TimerEnabled:=false; Application.MessageBox('Надоело бродить! Пойду-ка на таран...','Божий бык',0); TimerEnabled:=true; taran:=true; sbt:=0; for i:=0 to FieldWidth-1 do // очищаем память for j:=0 to FieldHeight-1 do memory[i,j]:=0; end; // отображаем текущее состояние быка Form1.StatusBar1.Panels[0].Text:='Жизней: '+inttostr(lifes); Form1.StatusBar1.Panels[1].Text:='Шагов: '+inttostr(stepcount); end; // конец процедуры Вот, собственно, и весь алгоритм. При ближайшем рассмотрении оказалось, что все достаточно просто и понятно. Основной идеей в этом алгоритме поиска пути является использование понятия «вес», характеризующего, насколько выгодна та или иная позиция.
Я рассмотрел алгоритм поиска пути и его реализацию достаточно подробно, специально для того, чтобы указать на богатство выбора решений. Ссылки по теме статьи
|
||||||||||||||||||||||||||
|