Метод оптимизации модели мобильного робота для системы эволюционного моделирования

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

Проанализировав эволюционные системы, установлено, что в модели робота существует избыточные компоненты, что приводит к следующим недостаткам:

• отсутсвие средств анализа моделей;

• большие временные затраты для анализа модели;

• неудобство визуализации модели в пространстве.

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

• разработка подсистемы анализа моделей;

• минимизация количества вершин и связей;

• минимизация площади изображения;

• минимизация вершин, влияние которых на выходные значения не превышает заданной погрешности.

В результате работы был написан модуль, позволяющий:

• визуализировать модели мобильных роботов на графе;

• осуществлять "слепые" вершин (вершины, не имеющие путей к выходным вершинам);

• отсечь вершины, влияние которых на выходные значения не превышает заданной погрешности.

Разработка модуля оптимизации модели мобильных роботов

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

В системе реализованы следующие основные функции:

1. Оптимицация модели робота

• отсечение маловажных вершин – вершин, не имеющих путей к выходным вершинам;

• отсечение вершин, влияние которых на выходные значения не превышает заданной погрешности.

2. Визуализация модели мобильных роботов

• изображать на 2D-графике модели робота с характеристиками и изображениями и связи между ними;

• изображать на матрице смежности количество связей между двумя моделями;

• изображать на матрице инциденций направление связей.

Визуализация модели мобильных роботов на графе

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

Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

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

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

Рисунок 2 - Структура описания визуализация графов

Для визуализации графов необходимо узнать:

• количество связей между двумя моделями;

• направление связей.

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

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

Оптимизации модели робота

Дан ориентированный граф G, множество вершин которого V и множество рёбер - E. Петли и кратные рёбра допускаются. Обозначим через n – количество вершин графа, через m – количество рёбер. Требуется найти все пути между двумя заданными вершинами и отсечение вершин, не имеющих путей к выходным вершинам.

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

• минимизации избыточных компонентов, которые не имеют путей к выходным компонентам;

• минимизация компонент, влияние которых на выходные значения не превышает заданной погрешности;

• минимизация площади изображения.

В соответствии с этими критериями модуль оптимизации модели робота должен выполнять следующие функции:

• отсечение "слепых" вершин вершин, не имеющих путей к выходным вершинам;

• отсечение вершин, влияние которых на выходные значения не превышает заданной погрешности.

Метод отсечения "слепых" вершин это процедура нахождения всех путей между двумя заданными вершинами. Мы используем алгоритм поиска в ширину (обход в ширину, breadth-first search) — это один из основных алгоритмов на графах.

Алгоритм работает за O(n + m), где n— число вершин, m— число рёбер.

На вход алгоритма подаётся заданный граф и номер стартовой вершины s. Граф может быть как ориентированным, так и неориентированным, для алгоритма это не важно.

Сам алгоритм можно понимать как процесс "поджигания" графа: на нулевом шаге поджигаем только вершину s. На каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей; т.е. за одну итерацию алгоритма происходит расширение "кольца огня" в ширину на единицу (отсюда и название алгоритма).

Более строго это можно представить следующим образом. Создадим очередь , в которую будут помещаться горящие вершины, а также заведём булевский массив used[], в котором для каждой вершины будем отмечать, горит она уже или нет (или иными словами, была ли она посещена).

Изначально в очередь помещается только вершина , и used[s] = true, а для всех остальных вершин used[s] = false. Затем алгоритм представляет собой цикл: пока очередь не пуста, достать из её головы одну вершину, просмотреть все рёбра, исходящие из этой вершины, и если какие-то из просмотренных вершин ещё не горят, то поджечь их и поместить в конец очереди.

В результате поиска в ширину находятся все пути между двумя заданными вершинами в ориентированом графе.

Рисунок 4 – Метод отсечения "слепых" вершин

Литература:

1. Робототехника [Электронный ресурс]. – 2006. – Режим доступа: http://www.prorobot.ru/12/robot-it-is.php

2. Робот [Электронный ресурс]. – 2008. – Режим доступа: http://ru.wikipedia.org/wiki/%D0%A0%D0%BE%D0%B1%D0%BE%D1%82

3. Робот для программиста [Электронный ресурс]. – 2007. – Режим доступа: http://robot.paccbet.ru/robot_for_programmer.php.htm

4. Алгоритм поиска пути для роботов [Электронный ресурс]. – 2007. – Режим доступа: http://robot.paccbet.ru/robot_path.php.htm

5. Финн, В.К. Правдоподобные выводы и правдоподобные рассуждения / В.К.Финн. – М.: ВИНИТИ, 1988. - Т. 28. – 180 с. – (Итоги науки и техники. Сер. «Теория вероятностей. Математическая статистика. Теоретическая кибернетика»).

6. Искусственный интеллект. В 3 т. Т. 2. Модели и методы: справочник/ под ред. Д. А. Поспелова. – М.: Радио и связь, 1990. – 304 с.