Библиографическое описание:

Чудинов В. А. Об одном из методов построения маршрута для подвижного робота // Молодой ученый. — 2016. — №15. — С. 209-211.



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

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

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

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

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

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

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

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

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

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

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

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

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

3. Будущая точка и все вершины, инцидентные настоящей точке, не должны лежать по разные стороны от прошлого пути.

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

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

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

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

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

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

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

Литература:

  1. Поезжаева Е. В. // Теория механизмов и механика систем машин. Промышленные роботы: учеб. пособие: в 3 ч. / Е. В. Поезжаева. — Пермь: Изд-во Перм. Гос. техн. ун-та, 2009. – Ч. 2. – 185.
  2. Поезжаева Е. В. // Теория механизмов и механика систем машин. Промышленные роботы: учеб. пособие: в 3 ч. / Е. В. Поезжаева. — Пермь: Изд-во Перм. Гос. техн. ун-та, 2009. – Ч. 3. – 164.
  3. Берж К. Теория графов и ее применение. М., Изд. иностр. лит., 1962.

Обсуждение

Социальные комментарии Cackle