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

Нго К. Х., Шабалина О. Метод оптимизации модели мобильного робота для системы эволюционного моделирования [Текст] // Технические науки в России и за рубежом: материалы Междунар. науч. конф. (г. Москва, май 2011 г.). — М.: Ваш полиграфический партнер, 2011. — С. 17-20.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


(1) – Если верши на совпадает с конечной вершиной.

(2) – Если значение вершинные значения равны нулю и вершина непроверенных.


Рисунок 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 с.


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

Обсуждение

Социальные комментарии Cackle
Задать вопрос