Оптимизация проведения проверки соответствия среды агента по его карте
Аннотация
В настоящее время одной из основных проблем теоретической кибернетики является проблема взаимодействия управляющей и управляемой систем (управляющего автомата и его операционной среды). Взаимодействие таких систем представляется как процесс перемещения автомата по помеченному графу среды. Автомат, находясь в вершине графа, воспринимает некоторую информацию о метках локальной окрестности этой вершины. На основании воспринятой информации автомат передвигается в некоторую вершину графа, смежную с исходной. При различных способах взаимодействия автомата и графа и различной априорной информации возникает проблема анализа свойств графа моделирующего операционную среду. Для решения этой проблемы в настоящем имеются несколько основных подходов. Один из подходов возник в рамках изучения проблемы навигации мобильных роботов и основывается на том, что операционная среда рассматривается как конечный неориентированный граф с помеченными концами ребер.
К фундаментальным задачам навигации мобильных роботов относится задача исследования неизвестной операционной среды или построения карты (exploration, map building), задача проверки соответствия карты и среды или контроля карты (map validation) и задача определения местоположения мобильного робота в известной операционной среде или самолокализации (robot self-location).
В настоящей работе рассматривается проблема контроля карты, представленной в виде графа с помеченными вершинами. Она актуальна как в теоретическом, так и в прикладном аспекте. Теоретическая важность заключается в применении методов теории автоматов при анализе графов, прикладная – в недостаточной исследованности данной проблемы, которая еще далека от разрешения вследствие большой вычислительной сложности и избыточности контрольных тестов.
Пусть G=(G, E(G), M, µ, g0) конечный, просто, связный, неориентированный граф с помеченными вершинами, где G – конечное множество вершин, E(G) ⊆ GxG – множество рeбер, М – множество меток,s |M|=m, µ: G→M – сюрьективная функция разметки. Окресность Og вершины g ∈ G – множество, состоящее из самой вершины g и всех вершин смежных с ней. Граф G детерминирован или D-граф, если для любой вершины geG и любых вершин s,t ∈ Og, из s*t следует µ(s) ≠ µ(t). Граф G называется приведенным, если все его вершины попарно отличимы. Последовательность меток вершин w= µ(g0).. µ(gk), соответствующий пути g0…gk будем называть словом, и через d(w) обозначим длину слова w. Языком Lg назовем множество всех слов, порождаемых вершиной ∪g∈GLG, а языком LG – объединение языков всех вершин u Lc . Графы G и Н называются эквивалентными, если 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)), где s ∈ G(Ki(P)) и G(Rt) ⊆ G(Ki(P)). Поскольку длина d(w) слова идентификатора w состояния s в общем случае неограниченна [2], выделяя множества подграфов K(P) ближайших к полным графам, получим минимальные по мощности подмножества меток |Mi(Ki(P))|=mi, содержащихся в слове w(s) идентификатора вершины s ∈ G(Ki(P)) и контрольном эксперименте Ki(P), что уменьшает длину контрольного эксперимента для Ki(P). Однако, использование разбиения графа G на множество пографов К(Р) усложняет применение предлагаемого метода построения идентификаторов и контрольного эксперимента.
Литература
1. Сапунов С.В. Проверка соответствия карты при навигации мобильных роботов / С.В. Сапунов //Искусственный интеллект. – 2006. – №6.– С. 77–685.
2. Грунский И.С. Синтез и идентификация автоматов / И.С. Грунский, В.А Козловский – К.: Наукова думка, 2004. – 245 с.
3. Сапунов С.В. Анализ графов с помеченными вершинами / С.В. Сапунов // Дисс. канд. физ.-мат. наук: 27.09.07. – Донецк.: 2007. – 150 с.
4. Гилл А. Введение в теорию конечных автоматов / A. Гилл – М.: Наука, 1966. – 272 с.
Надійшла до редакції 2010 р.