Оптимизация проведения проверки соответствия среды агента по его карте
Аннотация
В настоящее время одной из основных проблем теоретической кибернетики является проблема взаимодействия управляющей и управляемой систем (управляющего автомата и его операционной среды). Взаимодействие таких систем представляется как процесс перемещения автомата по помеченному графу среды. Автомат, находясь в вершине графа, воспринимает некоторую информацию о метках локальной окрестности этой вершины. На основании воспринятой информации автомат передвигается в некоторую вершину графа, смежную с исходной. При различных способах взаимодействия автомата и графа и различной априорной информации возникает проблема анализа свойств графа моделирующего операционную среду. Для решения этой проблемы в настоящем имеются несколько основных подходов. Один из подходов возник в рамках изучения проблемы навигации мобильных роботов и основывается на том, что операционная среда рассматривается как конечный неориентированный граф с помеченными концами ребер.
К фундаментальным задачам навигации мобильных роботов относится задача исследования неизвестной операционной среды или построения карты (exploration, map building), задача проверки соответствия карты и среды или контроля карты (map validation) и задача определения местоположения мобильного робота в известной операционной среде или самолокализации (robot self-location).
В настоящей работе рассматривается проблема контроля карты, представленной в виде графа с помеченными вершинами. Она актуальна как в теоретическом, так и в прикладном аспекте. Теоретическая важность заключается в применении методов теории автоматов при анализе графов, прикладная - в недостаточной исследованности данной проблемы, которая еще далека от разрешения вследствие большой вычислительной сложности и избыточности контрольных тестов.
Пусть G=(G, E(G), M, µ, g0) конечный, просто, связный, неориентированный граф с помеченными вершинами, где G - конечное множество вершин, E(G)czGxG - множество р?бер, М - множество меток, |M|=m, µ: G^M -сюрьективная функция разметки. Окресность Og вершины geG - множество, состоящее из самой вершины g и всех вершин смежных с ней. Граф G детерминирован или D-граф, если для любой вершины geG и любых вершин s,teOg, из s*t следует µ(в) ф µ(t). Граф G называется приведенным, если все его вершины попарно отличимы. Последовательность меток вершин w= µ(go).. µ(gk), соответствующий пути g0…gk будем называть словом, и через d(w) обозначим длину слова w. Языком Lg назовем множество всех слов, порождаемых вершиной g, а языком LG -объединение языков всех вершин u Lc . Графы G geG и Н называются эквивалентными, если LG=LH [1]. Граф G будем называть эталоном. Пусть R -подграф эталона и t - фиксированная метка подграфа. Подграф с фиксированной меткой обозначим Rt и назовем идентификатором метки s эталона, если выполняется условие (p(t)=s, а w(s) -словом идентификатора. Пусть Р подграф графа G, пусть также F(G) - класс всех подграфов графа G.
Пусть граф U(P) - полный граф, такой что |G(P)|=|G(U)|. Введем понятие расстояния между графами Р и U как отношение |E(P)|/|E(U)|=k. Пусть К(Р) множество всех подграфов G таких, что |E(Ki(P))|/|E(Ki (U))|=min. Предлагается для определения окрестности состояния s, являющегося его идентификатором, использовать множество G(Ki(P)), где seG(Ki(P)) и G(Rt)cG(Ki(P)). Поскольку длина d(w) слова идентификатора w состояния s в общем случае неограниченна[2], выделяя множества подграфов K(P) ближайших к полным графам, получим минимальные по мощности подмножества меток |Mi(Ki(P))|=nii, содержащихся в слове w(s) идентификатора вершины seG(Ki(P)) и контрольном эксперименте Ki(P), что уменьшает длину контрольного эксперимента для Ki(P). Однако, использование разбиения графа G на множество пографов К(Р) усложняет применение предлагаемого метода построения идентификаторов и контрольного эксперимента.
Литература
1. Сапунов С.В. Проверка соответствия карты при навигации мобильных роботов//Искусственный интеллект. –2006.– №6.– С.677–685.
2. Грунский И.С., Козловский В.А. Синтез и идентификация автоматов. – К.: Наукова думка, 2004. – 245с.
3. Сапунов С.В. Анализ графов с помеченными вершинами: Дисс. канд. физ.-мат. наук: 27.09.07. – Донецк.: 2007. – 150 с. 4. Гилл А. Введение в теорию конечных автоматов. – М.: Наука, 1966. – 272с.