5. СРЕДЫ И ЯЗЫКИ

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

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

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

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

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

5.1. Автомат и среда

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

Входной алфавит

Внутренний алфавит (множество состояний автомата)

Выходной алфавит .

Функция переходов , записываемая так же, как

Функция выходов , записываемая так же, как

Начальное состояние Обычно будем полагать, что

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

Таким образом, автомат перерабатывает последовательности еаап... о в последовательности где Если на автомат была подана последовательность то он перейдет в состояние Если на него была подана последовательность то он перейдет в состояние Если на него была подана последовательность то он перейдет в состояние Говорят при этом, что последовательность ведет в состояние начального состояния Произвольную последовательность во входном

Ответ на этот вопрос состоит в следующем. Если множество удовлетворяет условиям полноты, непротиворечивости и регулярности, то можно построить автомат, реализующий множество (язык S). Сформулируем условия полноты, непротиворечивости и регулярности для множества

Условия полноты. Для всякой последовательности всякое ее начало также принадлежит

Условия непротиворечивости. Не существует ни одной пары последовательностей таких, что

Условия регулярности. Любая последовательность может бьпъ получена из пустой последовательности только в результате последовательного приписывания справа (конкатенаций) конечных или бесконечных циклических последовательностей в алфавите А.

5.2.1. Сокращение числа состояний

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

Отношение если для всех а, таких, что

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

Множество классов эквивалентности можно использовать для построения автомата, реализующего множество 5, на основании следующих свойств классов эквивалентности являющихся следствием условий полноты, непротиворечивости и регулярности множества последовательностей действий

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

Свойство связности. Для любого класса существует хотя бы одна последовательность действий , такая, что

Свойство недоопределенности. Если множество допустимых последовательностей совпадает с множеством входных последовательностей т.е. то существует единственный класс эквивалентности все последовательности которого не принадлежат множеству Р, т.е. . Для определенности будем считать, что этот единственный класс последовательностей есть Из этого свойства также следует, что пересечение класса с множеством Р пусто а все остальные классы включаются в множество с Р). Построение автомата (обозначим его реализующего язык может быть осуществлено следующим образом. Классы эквивалентности отношения объявляются соответственно состояниями автомата Если а О, то состояние переходит в состояние т.е. если то где — функция переходов. Функция переходов однозначна вследствие свойства однозначной продолжаемости. Функцией выходов автомата М является функция где Функция выходов автомата М однозначна вследствие условия непротиворечивости. Начальным состоянием автомата М является состояние соответствующее классу эквивалентности содержащему пустую последовательность е. Вследствие свойства связности автомат М будет связным. Таким образом, автомат М имеет к состояние, каждое их которых соответствует одному из классов эквивалентности. Поскольку состояние соответствует классу то это означает, что для любой последовательности а имеет место и этот класс единственный. Автомат М, реализующий язык отличается от автомата М отсутствием в нем состояния и соответственно переходов в него. Множество состояний автомата М обозначим В, а автомата

5.2.2. Пример сокращения числа состояний

Пусть задано следующее множество простым перечислением последовательностей

Тогда, согласно определению,

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

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

Проверка на продолжениях длины 0:

Проверка на продолжениях длины 1:

Проверка на продолжениях длины 2:

Проверка на продолжениях длины 3:

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

Сопоставим классы эквивалентности соответственно состояниям автомата Поскольку последовательности множества принадлежат классу то т.е. автомат М, находящийся в состоянии при совершении действия о, остается в том же состоянии. Остальные последовательности множества принадлежат классу, который нас в данном случае не интересует (классу при данного примера). Далее, поскольку входные последовательности множества принадлежат классу то и т. д. В результате получим автомат М, граф переходов которого показан на рис. 5. 1. Начальным состоянием

Рис. 5.1. Граф переходов автомата М

этого автомата является состояние,

Значение функции выхода указано рядом с соответствующим состоянием.

Таким образом, для построения автомата М на рис. 5. 1 использовался следующий алгоритм.

Алгоритм разбиения последовательностей на классы эквивалентности:

а) принять Задать множество

б) объявить множество

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

г) считать равным , а Рравным перейти к выполнению пункта в) с новыми и Р,

д) если то перейти к пункту е). В противном случае принять равным и перейти к пункту б) с новым

е) отождествить полученные классы эквивалентности с внутренними состояниями автомата Для каждого действия и каждого класса эквивалентности такого что построить на графе переходов автомата дугу Дополнить полученный граф переходов отметкой каждой вершины функции Перейти к следующему пункту;

ж) конец.