Известия РАН. Теория и системы управления, 2019, № 5, стр. 87-107

Введение. Одной из актуальных проблем искусственного интеллекта является разработка эффективных моделей представления и обработки знаний автономного интеллектуального робота (АИР) для планирования целенаправленного поведения в различных по сложности априори недоопределенных условиях проблемной среды (ПС). Эффективное решение данной проблемы позволяет создавать АИР, способных целенаправленно функционировать в труднодоступных и агрессивных для человека ПС, например, подводных и космических роботов, роботов спелеологов, роботов для проведения различных работ на опасной для человека местности и т.д.

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

Необходимо отметить, что для создания АИР, способных целенаправленно функционировать в априори недоопределенных, реальных ПС, решающую систему робота по аналогии с человеком [1] целесообразно наделить способностями наглядно-действенного, наглядно-образного и понятийного мышления [2], соответственно позволяющими решать следующие классы задач поведения.

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

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

3. Робот, находясь в ПС, непосредственно не воспринимает ситуацию, в которой достигается заданная ему цель поведения. В таких условиях, обработав заложенные в память знания на основе различных рассуждений, АИР должен сформировать план целенаправленного полифазного поведения, предусматривающий полную смену текущих ситуаций ПС в заданной последовательности после достижения в каждой из них определенной подцели, связанной с достижением общей цели [4].

Следует также отметить, что на начальном этапе развития наиболее широкое распространение в системах искусственного интеллекта различного назначения, в том числе и в системах вывода решений АИР, получили модели представления и обработки знаний, основанные на использовании логики предикатов первого порядка. Например, в [5] предложена адаптивная стратегия логического вывода в недоопределенных ПС; в [6] рассмотрены возможности применения логики предикатов первого порядка для представления и обработки знаний на примере отечественных и зарубежных решателей задач различного назначения; в [7] изложена общая теория и проблемы, связанные с автоматическим доказательством теорем; в [8] проведен глубокий анализ, показаны возможности и проблемы, связанные с применением логики предикатов первого порядка, а в [9–11] приведены основные фундаментальные достижения зарубежных исследователей в области применения логики предикатов первого порядка в системах искусственного интеллекта. В [12] в рамках логического подхода разработаны эффективные процедуры дедуктивного вывода в немонотонных средах и т.д.

Однако эффективное применение организованных на основе логики первого порядка моделей представления и обработки знаний для планирования целенаправленного поведения АИР в априори недоопределенных условиях ПС ограничено следующими основными проблемами:

необходимостью задания подробной модели представления знаний о закономерностях ПС для вывода решений [13, 14];

отсутствием возможности использования в моделях представления знаний предикатов второго и большего порядков, что в свою очередь значительным образом снижает функциональные возможности построенных на их основе интеллектуальных решателей проблем для автономных роботов [7, 15];

трудоемкостью вывода решений сложных задач в процессе обработки знаний, который сводится к доказательству теорем методом перебора [8, 15]. Даже если частично упорядочить такой перебор на основе различных стратегий логического вывода, то процедуры планирования поведения АИР, основанные на применении автоматического доказательства теорем в логике предикатов первого порядка, все равно остаются в общем случае с экспоненциальной сложностью. Этот недостаток обусловлен тем, что в логике предикатов первого порядка не используется семантическая составляющая в формальном описании объектов, событий и закономерностей ПС как в моделях представления знаний, так и в процедурах их обработки в процессе вывода решений. Правда, существенный вклад в снятие данной проблемы дедуктивного вывода внесен в работе [16], в которой предложен алгоритм дедукции, основанный на трансформации семантических сетей, обеспечивающей возможность организации нескольких видов параллельного вывода и позволяющей значительным образом снизить сложность процесса доказательства теорем. Однако, учитывая относительно невысокие вычислительные ресурсы бортовой ЭВМ автономного робота и то, что данный подход не снимает полностью проблемы сложности вывода решений связанной с использованием логики предикатов первого порядка, его применение ограничено для организации планирования поведения АИР в априори недоопределенных условиях ПС.

Отмеченные выше обстоятельства обусловили переход к новой парадигме развития логического подхода к созданию искусственного интеллекта, связанной с использованием специальных моделей представления знаний, с применением нечетких логик для их обобщения и обработки [2, 17, 18]. Однако, несмотря на многоплановость исследований в этом направлении, проблема создания эффективных процедур планирования целенаправленного поведения АИР в априори недоопределенных ПС с линейной сложностью вывода решений сегодня остается открытой [18, 19].

Рассматривая вопросы, связанные с генерацией новых знаний для вывода решений АИР в процессе целенаправленного поведения в недоопределенных условиях ПС, следует отметить, что:

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

наиболее близкой по своему содержанию к проблеме автоматической генерации новых знаний следует отнести проблему их пополнения, для решения которой в настоящее время широкое применение нашли следующие три принципа: построение моделей здравого смысла [20], использование сценариев [21] и псевдофизических логик [22].

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

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

К одной из попыток совместить процедуры вывода решений и пополнения знаний в рамках одной модели представления знаний АИР можно отнести применение миварных технологий [23]. Однако предложенная в этом случае модель представления знаний и процедуры вывода не предусматривают решения следующих важных задач, существенно влияющих на эффективность планирования целенаправленного поведения АИР в априори недоопределенных условиях функционирования.

1. Выявления различий между текущей и целевой ситуациями ПС и автоматического построения на этой основе плана целенаправленного поведения [13, 24, 25].

2. Автоматического определения порядка устранения различий, наблюдаемых АИР, между фактической и целевой ситуацией ПС в процессе планирования поведения в реальном времени [26]. В результате теряется основное преимущество использования продукционных моделей представления знаний в решателях проблем, связанное с построением планов целенаправленного поведения АИР в априори недоопределенных условиях ПС с линейной сложностью вывода. Это обусловлено тем, что при произвольном выборе различия, с устранения которого АИР начинает строить план преобразования текущей в целевую ситуацию ПС, поиск решения сложной задачи целенаправленного поведения, как правило, сводится к полному перебору. Кроме того, в формируемом в этом случае плане целенаправленного поведения могут возникать циклы цепочек непродуктивных действий, которые необходимо удалить до начала его реализации.

3. Выделения в ПС участка, который непосредственно связан с достижением текущей цели или подцели поведения [27].

4. Принятия решений по аналогии, что не позволяет получать новые сведения об объектах и событиях, наблюдаемых в ПС, на основе имеющихся в модели знаний, когда такая необходимость возникает в процессе автоматического построения плана целенаправленного поведения в априори недоопределенных условиях функционирования [24, 28].

В настоящей работе предлагается модель представления и автоматической генерации новых знаний, позволяющая АИР планировать целенаправленное поведение в недоопределенных условиях ПС при сочетании наглядно-образного мышления с отдельными элементами понятийного мышления. В основе построения разработанной модели используется логика условно-зависимых предикатов [29] (язык формализации приведен в Приложении), позволяющая представлять декларативные и процедурные знания АИР безотносительно к конкретной предметной области и обойти в достаточно полной мере отмеченные выше недостатки известных логических моделей. В этом случае автоматическое построение плана целенаправленного поведения АИР в априори недоопределенной ПС сводится к выполнению следующих основных этапов:

означивания предметных переменных в условно-зависимых предикатах модели представления знаний находящимися в ПС объектами с целью адаптации имеющихся у робота сведений общего назначения к текущим условиям функционирования;

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

Генерация новых знаний в данной модели также опирается на означивание условно-зависимых предикатов, с помощью которых построены типовые конструкции представления декларативных и процедурных знаний, и сводится к доказательству выполнимости формул с линейной сложностью в полученной таким образом фактической модели закономерностей ПС с учетом заданной цели поведения. Например, в работе [30] предложены процедуры пополнения и получения новых знаний АИР на основе логики условно-зависимых предикатов путем вывода сложных умозаключений.

1. Модель представления и генерации новых знаний АИР. В логике условно-зависимых предикатов область допустимых значений каждой предметной переменной ${{y}_{i}}({{X}_{i}}) \in Y,Y = \{ {{y}_{i}}({{X}_{i}})\} $, $i = \overline {1,m} $, в условно-зависимых формулах (далее – просто переменные и формулы) определяется множеством характеристик X_i. В свою очередь каждый объект или событие ПС $O = \{ {{o}_{j}}({{X}_{j}})\} $, $j = \overline {1,{{m}_{1}}} $, также определяется множеством X_j описывающих их характеристик. Означивание предметной переменной ${{y}_{i}}({{X}_{i}})$ в произвольной формуле логики условно-зависимых предикатов допускается различными объектами ПС ${{o}_{j}}({{X}_{j}})$ тогда и только тогда, когда они обладают множеством характеристик X_i, т.е. для них выполняется условие ${{X}_{i}} \subseteq {{X}_{j}}$ [29]. При этом получаемое в результате высказывание является истинным. Например, формула “Летать (птицы (основные характеристики птиц, развитые крылья, отсутствие повреждений))” становится истинным высказыванием только в том случае, когда подставляемая в нее константа, например “Воробей”, имеет развитые крылья и у него отсутствуют повреждения.

Таким образом, в логике условно-зависимых предикатов, в результате означивания произвольной n – местной формулы $M[{{y}_{1}}({{X}_{1}}),\; \ldots ,\;{{y}_{k}}({{X}_{k}}),\; \ldots ,\;{{y}_{n}}({{X}_{n}})]$, получаемое высказывание истинно тогда и только тогда, когда для объектов ПС ${{o}_{k}}({{X}_{{ok}}})$, $k = \overline {1,n} $, используемых для означивания входящих в нее предметных переменных ${{y}_{k}}({{X}_{k}})$, выполняются условия ${{X}_{k}} \subseteq {{X}_{{ok}}}$, где ${{X}_{{ok}}}$, ${{X}_{k}}$ – множества характеристик, соответственно описывающих объект проблемной среды ${{o}_{k}}({{X}_{{ok}}})$ и предметную переменную ${{y}_{k}}({{X}_{k}})$. Сами же условно-зависимые предикаты непосредственно не интерпретируются, а в процессе планирования поведения АИР проверяется их выполнимость в заданной модели ПС по истинностному значению высказываний, получаемых в результате означивания в них предметных переменных объектами из этой модели.

Рассмотрим различные формулы логики условно-зависимых предикатов, которые позволяют представить знания АИР безотносительно к конкретной предметной области.

Пусть даны две формулы: ${{P}_{1}}(y({{X}_{1}}))$ – “Быть (живым существом $y({{X}_{1}})$)” и ${{P}_{2}}({{f}_{i}}(y({{X}_{{fi}}})))$ – “Уметь летать $(y({{X}_{{fi}}}))$”. Здесь f_i – функциональный символ, означающий, что все объекты ПС, обладающие характеристиками ${{X}_{{fi}}}$, могут летать. Связывая между собой данные формулы конъюнкцией, получим формулу $D = {{P}_{1}}(y({{X}_{1}}))\& {{P}_{2}}({{f}_{i}}(y({{X}_{{fi}}})))$, которая означает “Быть живым существом и уметь летать”. Данная формула является выполнимой, если ${{X}_{{fi}}} \subseteq {{X}_{1}}$, в противном случае она будет противоречивой.

Определение 1. Формула ${{P}_{1}}({{y}_{1}}({{X}_{1}}))\& {{P}_{2}}({{f}_{i}}(y({{X}_{{fi}}})))$ называется условно-зависимым логическим дополнением (далее – просто дополнение) первого типа формулы ${{P}_{1}}({{y}_{1}}({{X}_{1}}))$ и обозначается ${{P}_{1}}({{y}_{1}}({{X}_{1}}),{{f}_{i}}({{X}_{{fi}}}))$, если выполняется условие ${{X}_{{fi}}} \subseteq {{X}_{1}}$.

Таким образом, на основе дополнений первого типа АИР может пополнять свои знания о различных объектах и событиях ПС, например, определить, обладает или не обладает тот или иной объект умением летать. Ответ на данный запрос будет утвердительным, если для дополнения ${{P}_{1}}({{y}_{1}}({{X}_{1}}),{{f}_{i}}({{X}_{{fi}}}))$ и объекта ${{o}_{j}}({{X}_{j}})$ выполняется условие ${{X}_{1}} \subseteq {{X}_{j}}$. В результате такого означивания получается истинное высказывание ${{P}_{1}}({{o}_{j}}({{X}_{j}}),{{f}_{i}}({{X}_{{fi}}}))$ – “Объект ${{o}_{j}}({{X}_{j}})$ является живым существом, умеющим летать”.

Пусть даны два дополнения ${{Q}_{1}} = {{P}_{1}}(y({{X}_{1}}),{{f}_{1}}({{X}_{{f1}}}))$ и ${{Q}_{2}} = {{P}_{2}}(y({{X}_{2}}),{{f}_{2}}({{X}_{{f2}}}))$ первого типа.

Определение 2. Если для двух дополнений Q₁ и Q₂ выполняется условие $({{X}_{1}}\, \subset \,{{X}_{2}})\, \otimes \,({{X}_{{f2}}}\, = \,{{X}_{{f1}}})$, а осмысленные слова, биективно соответствующие предикатным символам Р₁ и Р₂, совпадают, то первое из них является обобщением второго, где знак $ \otimes $ означает необходимость одновременного выполнения обеих частей проверяемого условия.

Например, логическое дополнение “Быть (живым существом $y({{X}_{1}})$ и уметь летать)” в предметной области “живые существа” выступает обобщением логического дополнения “Быть (птицей $y({{X}_{2}})$ и уметь летать)”.

Пусть дополнение Q₁ – обобщение дополнения Q₂, тогда для данной пары логических дополнений можно доказать справедливость следующих утверждений.

Утверждение 1. Если дополнение Q₁, является обобщением дополнения Q₂, то множество объектов ПС ${{O}_{1}} \subset O$, определяющих область допустимых значений переменной $y({{X}_{1}})$, условно-зависимо расширяет множество объектов ПС ${{O}_{2}} \subset O$, которые удовлетворяют требованиям означивания переменной $y({{X}_{2}})$, т.е. ${{O}_{2}} \subset {{O}_{1}}$. В этом случае переменная $y({{X}_{1}})$ представляет собой условно-зависимое обобщение переменной $y({{X}_{2}})$, где область допустимых значений, например, предметной переменной $y({{X}_{2}})$ определяется объектами ПС ${{o}_{j}}({{X}_{j}}) \in O$, для которых выполняется условие ${{X}_{2}} \subseteq {{X}_{j}}$.

Доказательство. Справедливость данного утверждения следует из того, что, согласно определению 2, для мощностей множеств характеристик ${{X}_{1}}$ и ${{X}_{2}}$, соответственно описывающих переменные в формулах Q₁ и Q₂, выполняется условие $\left| {{{X}_{1}}} \right| < \left| {{{X}_{2}}} \right|$. Следовательно, количество объектов ПС, удовлетворяющих требованиям означивания переменной $y({{X}_{1}})$, определяемой меньшим количеством характеристик, будет больше количества объектов, удовлетворяющих требованиям означивания переменной $y({{X}_{2}})$, а из выполнения условия $({{X}_{1}} \subset {{X}_{2}}) \otimes ({{X}_{{f2}}} = {{X}_{{f1}}})$ следует, что ${{O}_{2}} \subset {{O}_{1}}$. Следовательно, утверждение 1 справедливо.

Утверждение 2. Пусть дополнение Q₁ представляет собой обобщение дополнения Q₂. Тогда, при означивании одной и той же константой $a({{X}_{a}})$ переменных, входящих в данные логические дополнения, если высказывание $Q_{1}^{*} = {{P}_{1}}(a({{X}_{a}}),{{f}_{1}}({{X}_{{f1}}}))$ ложно, то ложным будет и высказывание $Q_{2}^{*} = {{P}_{2}}(a({{X}_{a}}),{{f}_{2}}({{X}_{{f2}}}))$, а когда высказывание $Q_{2}^{*}$ является истинным, то истинным будет и высказывание $Q_{1}^{*}$.

Доказательство 1.  Допустим, что в результате означивания переменной в обобщении Q₁ константой $a({{X}_{a}})$ получено ложное высказывание $Q_{1}^{*}$. Следовательно, для данного дополнения и константы $a({{X}_{a}})$ условие ${{X}_{1}} \subseteq {{X}_{a}}$ не выполнимо. Тогда из условия, что дополнение Q₁ является обобщением дополнения Q₂, следует, что ${{X}_{1}} \subset {{X}_{2}}$. Следовательно, для дополнения Q₂ и константы $a({{X}_{a}})$ условие ${{X}_{2}} \subseteq {{X}_{a}}$ также не выполнимо.

2. Допустим, что при означивании переменной в дополнении Q₂ константой $a({{X}_{a}})$ получено истинное высказывание $Q_{2}^{*}$. Таким образом, для логического дополнения Q₂ и константы $a({{X}_{a}})$ верно условие ${{X}_{{f2}}} \subseteq {{X}_{2}} \subseteq {{X}_{a}}$.

Исходя из того, что дополнение Q₁ является обобщением дополнения Q₂, выполняется условие $({{X}_{{f1}}} = {{X}_{{f2}}}) \otimes ({{X}_{1}} \subset {{X}_{2}})$. Отсюда для дополнения Q₁ и константы $a({{X}_{a}})$ верно условие ${{X}_{{f1}}} \subseteq {{X}_{1}} \subseteq {{X}_{a}}$. Следовательно, при означивании переменной в дополнении Q₁ константой $a({{X}_{a}})$ в результате получается истинное высказывание $Q_{1}^{*}$.

3. Из п. 1, 2 с очевидностью следует справедливость утверждения 2.

Таким образом, допустимое означивание переменной в дополнении Q₂ различными объектами ПС порождает высказывания, которые являются частными примерами для дополнения Q₁.

В общем случае в условно-зависимых формулах допускается замена переменных на другие переменные с более узким уровнем общности, чем заменяемая переменная.

Пример 1. Пусть переменная $y({{X}_{5}})$ означает “Различные птицы”. Тогда в результате замены переменной $y({{X}_{1}})$ в логическом дополнении Q₁ – “Быть (живым существом $y({{X}_{1}})$), умеющим летать” на переменную $y({{X}_{5}})$ получим логическое дополнение ${{Q}_{3}} = {{P}_{1}}(y({{X}_{5}}),{{f}_{1}}({{X}_{{f1}}}))$ – “Быть (птицей $y({{X}_{5}})$), умеющей летать”. Полученное таким образом дополнение выполнимо, если переменные $y({{X}_{1}})$ и $y({{X}_{5}})$ удовлетворяют условию ${{X}_{1}} \subset {{X}_{5}}$. Следовательно, в результате проведения замены переменной $y({{X}_{1}})$ в дополнении Q₁ на переменную $y({{X}_{5}})$ получается дополнение Q₃, для которого исходное логическое дополнение будет обобщением.

Таким образом, в общем случае в произвольное дополнение ${{P}_{i}}(y({{X}_{i}}),{{f}_{1}}({{X}_{{f1}}}))$ допускается подстановка переменных $y({{X}_{j}})$, $j = \overline {1,n} $, вместо переменной $y({{X}_{i}})$, если переменная $y({{X}_{i}})$ является их обобщением.

Следовательно, заменяя в дополнении Q₃ переменную $y({{X}_{5}})$ на переменную “воробьи” – $y({{X}_{6}})$, получим логическое дополнение ${{Q}_{4}} = {{P}_{1}}(y({{X}_{6}}),{{f}_{1}}({{X}_{{f1}}}))$ – “Быть (воробьем $y({{X}_{6}})$, умеющим летать)”. Сформированное таким образом дополнение обладает меньшим уровнем общности, чем исходное дополнение.

Необходимо отметить, что по условию замены переменных в формулах другими переменными получаемые таким образом формулы являются выполнимыми в допустимой области значений входящих в них переменных только в том случае, когда исходная формула выполнима в этой области. Для высказывания $Q_{4}^{*} = {{P}_{1}}(a({{X}_{a}})$,  f₁(X_f1), которое получается в результате означивания переменной в дополнении Q₄ константой $a({{X}_{a}})$ – “Конкретный воробей”, все логические дополнения Q₁, Q₃ и Q₄ являются его обобщениями.

В этом случае дополнения Q₁, Q₃, Q₄ и высказывание $Q_{4}^{*}$ могут быть упорядочены в виде кортежа $M = \langle {{Q}_{1}};{{Q}_{3}};{{Q}_{4}};Q_{4}^{*}\rangle $ по уровню общности входящих в них переменных и констант, согласно следующему условию: ${{X}_{1}} \subset {{X}_{4}} \subset {{X}_{6}} \subseteq {{X}_{a}}$.

Пример 2. Кортеж М, сформированный на основе полученных выше формул, будет иметь следующее содержание: 〈(Живые существа y(X₁), умеющие летать (Х_f1)); (Птицы y(X₄), умеющие летать (Х_f1)); (Воробьи y(X₆), умеющие летать (Х_f1)); (Воробей а(Х_а) умеет летать (Х_f1))〉, где Х_f1 = = {основные характеристики живых существ, иметь развитые крылья, отсутствие повреждений}.

Пусть произвольный объект ПС ${{o}_{j}}({{X}_{j}})$ удовлетворяет требованиям означивания переменной ${{y}_{i}}({{X}_{i}})$ хотя бы в одном из дополнений, входящих в структуру кортежа M. Тогда, двигаясь по элементам кортежа M справа налево от высказывания, полученного в результате допустимого означивания объектом ${{o}_{j}}({{X}_{j}})$, АИР может обобщить свои знания о данном объекте, если это потребуется в процессе вывода решений.

Определение 3. Пусть дан произвольный кортеж M, состоящий из множества дополнений $Q$ первого типа. Назовем первое в кортеже M дополнение Q₁ порождающей его формулой и заметим, что в данной формуле множество характеристик ${{X}_{1}}$, определяющих ее переменную ${{y}_{1}}({{X}_{1}})$, имеет минимальную мощность $\left| {{{X}_{1}}} \right|$. Например, для приведенного выше кортежа М порождающей формулой является предикат “Быть (живым существом y(X₁)), умеющим летать (Х_f1))”.

Следует отметить, что используя родовидовые отношения [31] на основе элемента Q₁ кортежа М можно сгенерировать дерево G, каждая ветвь которого R_j, $j = \overline {1,m} $, строится и далее разветвляется на основе формул с переменными${{y}_{i}}({{X}_{i}})$, $i = \overline {1,n} $, для которых переменная в порождающей формуле представляет собой их обобщение. В этом случае формула ${{P}_{k}}({{y}_{{}}}({{X}_{k}}),{{f}_{1}}({{X}_{{f1}}}))$, которой помечена произвольная вершина ${{{v}}_{k}} \in {{R}_{j}}$, является обобщением всех нижестоящих формул ${{P}_{j}}({{y}_{j}}({{X}_{j}}),{{f}_{1}}({{X}_{{f1}}}))$ в ветви ${{R}_{j}}$ дерева G, так как для них выполняется условие ${{X}_{k}} \subset {{X}_{j}}$.

Например, пусть порождающая кортеж М формула Q₁ определяется переменной “Живые существа”, тогда на ее основе можно сгенерировать разветвленное дерево G с ветвями ${{R}_{j}} \in G$ на основе порождающих эти ветви формул, содержащих переменные “Птицы”, “Рыбы” и т.д.

Таким образом, декларативные знания, определяющие свойства и умения различного класса объектов, сформированные в виде множества соответствующих им деревьев G_h, $h = \overline {1,d} $, позволяют АИР эффективным образом обобщать или уточнять необходимые в процессе принятия решений знания об объектах произвольной проблемной среды.

Определим правила подстановки, которые обеспечивают возможность расширения имеющихся у АИР декларативных знаний об объектах ПС путем формирования различных ветвей R_j дерева ${{G}_{h}}$ на основе содержащихся в них формул.

Правило подстановки 1. Пусть задано дополнение ${{Q}_{1}} = {{P}_{1}}(y({{X}_{1}}),{{f}_{1}}({{X}_{{f1}}}))$ и множество условно-зависимых функциональных символов $F = \{ {{f}_{i}}({{X}_{{fi}}})\} $, $i = \overline {2,n} $, определяющих соответствующие им свойства и умения различных объектов ПС ${{o}_{j}}({{X}_{j}})$, для которых выполняется условие ${{X}_{{f1}}} \subset {{X}_{{f2}}} \subset {{X}_{{f3}}},\; \ldots ,\; \subset {{X}_{{fn}}} \subset {{X}_{1}} \subseteq {{X}_{j}}$. Тогда на основе формулы Q₁ можно сформировать сложное логическое дополнение путем рекурсивной подстановки в нее функциональных символов ${{f}_{2}}({{X}_{{f2}}}),{{f}_{3}}({{X}_{{f3}}}),\; \ldots ,\;{{f}_{n}}({{X}_{{f{\text{n}}}}})$. Порядок такой подстановки определяется порядком, заложенным в условие ${{X}_{{f1}}} \subset {{X}_{{f2}}} \subset {{X}_{{f3}}},\; \ldots ,\; \subset {{X}_{{fn}}}$. В результате получается сложное логическое дополнение ${{P}_{1}}[y({{X}_{1}}),{{f}_{1}}({{f}_{2}}({{f}_{3}},\; \ldots ,\;{{f}_{n}}({{X}_{{fn}}})))]$, которое позволяет пополнять знания АИР о различных объектах ПС на основе проверки истинностного значения следующего утверждения: “Объект ПС ${{o}_{j}}({{X}_{j}})$ обладает функциональными возможностями ${{f}_{1}}({{X}_{{f1}}}),{{f}_{2}}({{X}_{{f2}}}),\; \ldots ,\;{{f}_{n}}({{X}_{{fn}}})$”. Данное утверждение является истинным, если для произвольного объекта ПС ${{o}_{j}}({{X}_{j}})$ выполняется условие ${{X}_{1}} \subseteq {{X}_{j}}$. Например, на основе сложного логического дополнения АИР может определить по заданному множеству характеристик такие объекты ПС, которые одновременно могут ходить, плавать и летать.

Правило подстановки 2. Пусть дано сложное логическое дополнение P₁[y₁(X₁), ${{f}_{1}}({{f}_{2}}({{f}_{3}}, \ldots ,{{f}_{n}}({{X}_{{fn}}})))]$ и упорядоченное множество переменных $\left\langle {{{y}_{1}}({{X}_{1}}),{{y}_{2}}({{X}_{2}}),{{y}_{3}}({{X}_{3}}),\; \ldots ,\;{{y}_{m}}({{X}_{m}})} \right\rangle $, для которых выполняется условие $C = ({{X}_{1}} \subset {{X}_{2}} \subset {{X}_{3}},\; \ldots ,\; \subset {{X}_{m}})$. Тогда допустимой является замена переменой ${{y}_{1}}({{X}_{1}})$ на любую из переменных ${{y}_{2}}({{X}_{2}}),{{y}_{3}}({{X}_{3}}), \ldots ,\;{{y}_{m}}({{X}_{m}})$. Если такую замену производить в порядке, определяющемся условием C, то в результате можно получить следующую ветвь R_j дерева G:

где стрелками обозначены ребра ветви, соединяющие ее смежные вершины.

Следует отметить, что в полученной таким образом ветви R_j дерева ${{G}_{h}}$ каждое входящее в нее логическое дополнение является обобщением стоящей от него справа формулы.

Расширяемое на основе правил подстановки 1, 2 содержание формул в ветвях R_j деревьев G_k позволяет пополнять декларативные знания АИР путем означивания входящих в них переменных конкретными объектами ПС.

Рассмотрим принцип построения модели процедурных знаний АИР на основе формул логики условно-зависимых предикатов. Пусть даны следующие формулы:

${{F}_{1}} = {{P}_{1}}({\text{робот}},{{y}_{1}}({{X}_{1}}))$ – “Взять (робот, объект ${{y}_{1}}({{X}_{1}})$)”;

${{F}_{2}} = {{P}_{2}}({\text{робот}},{{y}_{2}}({{X}_{2}}))$ – “Подойти (робот, объект ${{y}_{2}}({{X}_{2}})$)”;

${{F}_{3}} = {{P}_{3}}({\text{робот}},{{y}_{3}}({{X}_{3}}))$ – “Проход от местоположения робота до объекта ${{y}_{3}}({{X}_{3}})$ должен быть свободен”.

Определение 4. Формула ${{F}_{1}}\& {{F}_{2}}\& {{F}_{3}}$ называется логическим дополнением второго типа формулы ${{F}_{1}}$ и обозначается как

если выполняется условие $({{X}_{2}} \subseteq {{X}_{1}}) \otimes ({{X}_{3}} \subseteq {{X}_{1}})$, позволяющее провести замену переменных ${{y}_{2}}({{X}_{2}})$ и ${{y}_{3}}({{X}_{3}})$ на переменную ${{y}_{1}}({{X}_{1}})$, где:

Х₁ – множество характеристик, которыми должны обладать объекты ПС, Х₁ = {a₁ – габаритные размеры объекта, при которых рабочий орган робота способен его захватить; a₂ – вес объекта, который не должен превышать грузоподъемности манипулятора робота; объект ${{y}_{1}}({{X}_{1}})$ не прикреплен к другому объекту и расположен на высоте в пределах рабочей зоны манипулятора робота};

${{P}_{1}}$ – идентификатор логического дополнения “Взять объект”;

${{b}_{1}}({{y}_{1}}({{X}_{1}}))$ – действие “Подойти к объекту ${{y}_{1}}({{X}_{1}})$”;

${{b}_{2}}({{y}_{1}}({{X}_{1}}))$ – действие “Захватить и поднять объект ${{y}_{1}}({{X}_{1}})$”.

Полученную таким образом формулу можно интерпретировать следующим образом: если для произвольного объекта ПС $o({{X}_{j}})$ высказывание ${{P}_{3}}\left[ {o({{X}_{j}})\& {{b}_{2}}(o({{X}_{j}}))\& {{b}_{1}}(o({{X}_{j}})} \right]$ является истинным (выполняется условие ${{X}_{1}} \subset {{X}_{j}}$, а на пути движения к этому объекту отсутствуют препятствия), то АИР может подойти, захватить и поднять данный объект.

Определение 5. Если для произвольных дополнений второго типа

верно условие $({{X}_{1}} \subset {{X}_{2}}) \otimes (P_{1}^{*} = P_{2}^{*}) \otimes ({{b}_{1}} = {{b}_{2}})$, то первое дополнение является обобщением второго дополнения, где $P_{1}^{*}$ и $P_{2}^{*}$ – условия, которые должны выполняться в ПС для успешной отработки роботом входящих в них действий.

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

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

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

Таким образом, для представления процедурных знаний АИР целесообразно использовать следующие две типовые конструкции логики условно-зависимых предикатов.

1. Дополнения второго типа, содержащие в своей структуре по одному действию. Это позволяет получить гибкую модель представления процедурных знаний в виде множества отдельных дополнений. Каждое такое дополнение включает описание требуемой ситуации, восприятие которой в ПС обеспечивает результативную отработку соответствующего ему действия. Однако использование только такой модели представления процедурных знаний АИР приводит к увеличению размерности пространства поиска решений в процессе планирования целенаправленного поведения.

2. В виде ТМП, например, имеющих следующую структуру (микропрограмма поведения ${{F}_{5}}$ – “Перенести объект в ПС”):

где $ \leftrightarrow $ – операция эквивалентности формул; ${{P}_{1}}$ – идентификатор ТМП – “Перенести объект”; ${{P}_{2}}$ – необходимое условие “В среде должен быть проход от местоположения робота к объекту ${{y}_{2}}({{X}_{2}})$” для результативной отработки действия ${{b}_{1}}$; ${{P}_{3}}$ – необходимые условия, которые одновременно должны выполняться в ПС для успешной отработки действия ${{b}_{2}}$, ${{P}_{3}}$ = {Объект ${{y}_{2}}({{X}_{2}})$ не прикреплен к другому объекту, он имеет вес и габаритные размеры соответственно не более $a_{1}^{*}$ и $a_{2}^{*}$ и расположен в пределах рабочей зоны манипулятора робота по высоте $h{\text{*}}$}; ${{P}_{4}}$ – необходимое условие “Из текущего местоположения объекта ${{y}_{2}}({{X}_{2}})$ должен быть проход к местоположению объекта ${{y}_{3}}({{X}_{3}})$” для результативной отработки действий ${{b}_{3}}$ и ${{b}_{4}}$; Z₅ – структурированное описание результатов отработки действий микропрограммы поведения, представленное, например, в виде семантической сети, построенной в пространстве состояний или в виде выполняющихся в среде условий.

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

2. Особенности проверки выполнимости формул в логике условно-зависимых предикатов. Заметим, что в общем случае общезначимых условно-зависимых формул в исчислении условно-зависимых предикатов нет, так как их истинностное значение определяется по результатам проверки выполнения заданного условия. Можно определить только монотонное множество констант (объектов ПС), на котором произвольная формула или ее различные дополнения будут принимать истинное значение. Другими словами, каждая формула, а, точнее, множества характеристик, определяющих входящие в нее переменные, позволяют выделить в произвольной предметной области монотонную область их допустимых значений, т.е. значений, при которых данная формула становится истинной. Таким образом, по аналогии с теоремами в логике предикатов первого порядка можно провести доказательство выполнимости формул в логике условно-зависимых предикатов на заданном множестве посылок (формул), определяющих текущую ситуацию ПС.

В общем же случае справедливость или опровержение того или иного отдельного утверждения в конкретных условиях ПС, логика условно-зависимых предикатов позволяет установить по истинности высказывания, получаемого в результате допустимого означивания переменных в соответствующей ему формуле объектами этой среды. Например, монотонной областью определения переменной в формуле “Быть (живым существом ${{y}_{i}}({{X}_{i}})$) и уметь летать” является множество объектов ПС ${{o}_{j}}({{X}_{j}}) \in O$, для которых выполняется условие ${{X}_{i}} \subseteq {{X}_{j}}$, где множество характеристик ${{X}_{i}}$ = {характеристики живого существа, иметь развитые крылья, повреждения отсутствуют}.

Определение 6. Произвольное дополнение первого или второго типа является условно-зависимо общезначимым на заданном множестве констант $A = \{ {{a}_{i}}({{X}_{{ai}}})\} $, $i = 1,m$, если для каждой из них ${{a}_{i}}({{X}_{{ai}}}) \in A$ и переменной данных дополнений верно условие ${{X}_{1}} \subseteq {{X}_{{ai}}}$.

Сформулируем свойство выполнимости формулы B, определяющей, например, цель поведения АИР, заданную безотносительно к конкретной предметной области и содержащую дополнение второго типа, на заданном множестве дополнений или формул $W = \{ {{W}_{1}},{{W}_{2}},\; \ldots ,\;{{W}_{i}},\; \ldots ,\;{{W}_{m}}\} $, описывающих, например, обобщенную модель текущей ситуации ПС.

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

Например, пусть дано множество истинных высказываний $S = \{ {{S}_{1}},{{S}_{2}},\; \ldots ,\;{{S}_{i}},\; \ldots ,\;{{S}_{m}}_{3}\} $ и формула B, соответственно определяющие фактическую модель текущих условий ПС и подцель поведения, заданную АИР в виде дополнения ${{F}_{6}}$. Допустим, роботу в процессе планирования целенаправленного поведения необходимо проверить в текущих условиях ПС возможность результативной отработки действия ${{b}_{1}}$ над ее определенным объектом. Для решения этой задачи и проводится доказательство выполнимости формулы B на заданном множестве высказываний S, определяющих текущее состояние ПС.

Утверждение 3. Действия АИР, содержащиеся в формуле B, являются выполнимыми в текущих условиях ПС, т.е. формула B есть логическое следствие множества истинных высказываний $S$ тогда и только тогда, когда для каждого предиката, входящего в ее структуру, во множестве формул S содержится такое высказывание ${{S}_{i}} \in S$, для которого данный предикат служит его обобщением.

Доказательство 1. Очевидно, что формула $B$ верна на множестве высказываний $S$, если истинным является сложное высказывание ${{S}_{1}}\& {{S}_{2}}\& ,\; \ldots ,\;\& {{S}_{i}}\& ,\; \ldots ,\;\& {{S}_{m}}\& B{\text{*}}$, где $B{\text{*}}$ – высказывание, полученное из формулы B путем означивания переменных во входящих в нее предикатах ${{F}_{i}} \in B$ объектами ПС из высказываний ${{S}_{i}} \in S$, $i = \overline {1,{{m}_{3}}} $, для которых данные предикаты представляют собой логическое обобщение.

2. Согласно утверждению 2, высказывание $B{\text{*}}$ является истинным. Следовательно, высказывание ${{S}_{1}}\& {{S}_{2}}\& ,\; \ldots ,\;\& {{S}_{i}}\& ,\; \ldots ,\;\& {{S}_{m}}\& B{\text{*}}$ также истинно. Таким образом, справедливость утверждения 3 доказана.

Следовательно, в основе проверки выполнимости произвольной формулы B, в которую входят отрабатываемые АИР действия, на заданном множестве формул $S$, определяющих текущую ситуацию ПС, лежит вывод, позволяющий установить, что формула $B$ является логическим следствием формул $S$.

Пример 3. Допустим, подводный АИР обладает техническим зрением, обеспечивающим ему возможность распознавать заданное множество объектов ПС. Пусть в среде наблюдается следующая исходная текущая ситуация S: робот на морском дне видит затонувший объект, имеющий высоту h₁, на котором лежит предмет $o(X)$, обладающий множеством характеристик Х, Х = {вес (а₁), габаритные размеры (а₂), не прикреплен к другому объекту} и корзину (К) подъемника, имеющую высоту ограждений, равную h₂, и служащую для поднятия с морского дна различных объектов.

Между местоположением АИР и объектом o(X) отсутствуют непреодолимые препятствия, т.е. от местоположения робота к объекту o(X) имеется свободный проход. Робот также может беспрепятственно перейти от местоположения объекта o(X) к подъемнику. Роботу необходимо перенести объект o(X) и положить его в корзину подъемника.

Таким образом, АИР в процедурной форме задана цель поведения – “Перенести объект o(X) к местоположению подъемника и опустить данный объект в его корзину”. Для достижения данной цели, согласно ее содержанию, АИР выбирает ТМП ${{F}_{5}}$. Данная типовая микропрограмма позволяет АИР выделить в ПС участок, на котором он будет непосредственно функционировать. Для этого выполняется означивание переменных в заданной роботу цели объектами ПС. В результате получается следующее множество высказываний, определяющих фактическую модель поведения АИР в текущей ситуации ПС S*:

“Подойти ((робот, o(X)), (проход свободен))”;

“Захватить (робот, o(X)), (не закреплен, имеет вес (${{a}_{1}} \leqslant a_{1}^{*}$) и габариты (${{a}_{2}} \leqslant a_{2}^{*}$), высота положения объекта (${{h}_{1}} \leqslant h{\text{*}}$))”;

“Подойти ((робот, КЗ), (проход свободен))”;

“Положить (робот, o(X), К), (высота стенок корзины (${{h}_{2}} \leqslant h{\text{*}}$))”.

Следовательно, в текущей ситуации ПС выполняются условия Р₂, Р₃ и Р₄, все полученные высказывания в результате означивания переменных в заданной цели являются истинными, так как каждый предикат в формуле ${{F}_{5}}$, очевидно, служит обобщением одного из истинных высказываний в исходном описании S текущей ситуации проблемной среды. Таким образом, ТМП ${{F}_{5}}$ непосредственно реализуется в текущих условиях ПС, и АИР остается только отработать содержащиеся в ней в заданном порядке действия для достижения стоящей перед ним цели.

Рассмотрим случай, когда между АИР и объектом ПС $o(X)$, а также между положением этого объекта и корзиной подъемника имеются непреодолимые препятствия, т.е. когда в среде не выполняются условия Р₃ и Р₄ реализуемой ТМП. В этом случае робот выбирает из памяти ТМП, позволяющую ему сформировать локально-оптимальную трассу движения вдоль прямой к местоположению заданных объектов, построенную, например, на основе алгоритмов планирования перемещения в среде с препятствиями [32]. Сформированные на базе данных алгоритмов ТМП хранятся в памяти АИР в виде типовых элементов представления процедурных знаний, которые выбираются для реализации в процессе планирования поведения по соответствующему им идентификатору – “наличие препятствий”.

Допустим, АИР необходимо в процессе формирования плана целенаправленного поведения для проверки выполнимости формулы $B$, согласно утверждению 3, получить новые знания безотносительно к конкретным условиям ПС. Решение данной задачи сводится к формированию множества дополнений ${{W}_{H}} = \{ {{W}_{j}}\} $, $j = \overline {1,k} $, необходимых для вывода решения требуемой задачи, на основе заданной роботу модели знаний, представляющей собой множество дополнений второго типа W и ТМП. Для этого интеллектуальным решателем АИР проверяется выполнимость формулы B, состоящей из логических дополнений ${{W}_{H}}$, на заданном множестве формул W. Если формула B окажется выполнимой на множестве формул W, то дополнения ${{W}_{H}}$ используются в дальнейшем как типовые элементы представления процедурных знаний АИР.

Определение 7. Дополнение второго типа, для определения которого проверяется выполнимость формулы $B$ на заданной АИР модели представления знаний, называется базовым дополнением этой формулы.

Определение 8. Если базовое дополнение ложно, то ложной является и формула $B$, которая представляет собой конъюнкцию базового дополнения ${{W}_{j}} \in {{W}_{H}}$ с множеством заданных формул, определяющих условия, выполнение которых в ПС необходимо для результативной отработки соответствующего ему действия ${{b}_{j}}({{X}_{j}})$.

Определение 9. Формула $B$ является выполнимой на множестве дополнений $W$ (логическим следствием формул W) тогда и только тогда, когда для заданного означивания I переменных в данных формулах они принимают истинное значение. Кроме того, верно условие, что для базового дополнения формулы $B$ имеется хотя бы одно дополнение ${{W}_{i}} \in W$, которое является его обобщением.

Утверждение 4. Формула $B$ выполнима на произвольном множестве формул W тогда и только тогда, когда для заданного означивания переменных I она принимает истинное значение, а формула ${{T}_{1}} = \sim {\kern 1pt} ({{W}_{1}}\& {{W}_{2}}\& ,\; \ldots ,\;\& {{W}_{i}}\& ,\; \ldots ,\;\& {{W}_{m}})\& B$ – ложное, а также верно условие, что множество формул W включает хотя бы одно дополнение второго типа ${{W}_{i}} \in W$, которое является обобщением для базового дополнения формулы $B$.

Доказательство 1. Пусть, для означивания

формула $B$ принимает истинное значение. Тогда если допустить, что формула $B$ выполнима на множестве формул W, то формула ${{T}_{1}} = \,\sim ({{W}_{1}}\& {{W}_{2}}\& , \ldots ,\;\& {{W}_{i}}\& ,\; \ldots ,\;\& {{W}_{m}})\& B$ по определению должна быть ложной. Отсюда и формула $\sim ({{W}_{1}}\& {{W}_{2}}\& ,\; \ldots ,\;\& {{W}_{i}}\& ,\; \ldots ,\;\& {{W}_{m}})$ – ложная, так как формула B для означивания ${{I}_{1}}$ – истинная. Следовательно, если формула B является истинной, то и формула ${{W}_{1}}\& {{W}_{2}}\& ,\; \ldots ,\;\& {{W}_{i}}\& ,\; \ldots ,\;\& {{W}_{m}}$ для означивания ${{I}_{1}}$ также истинна при условии, что формула ${{T}_{1}}$ является ложной.

2. Пусть высказывание, получаемое из формулы ${{W}_{i}} \in W,$ которая есть обобщение базового дополнения формулы B, для означивания ${{I}_{1}}$ является ложным. Следовательно, высказывание, получаемое из формулы B, согласно утверждению 2 для этого означивания, также будет ложным. Отсюда формула ${{T}_{1}}$ для означивания ${{I}_{1}}$ будет истинной, что противоречит условию выполнимости формулы B на множестве заданных дополнений W. Следовательно, формула B в этом случае невыполнима на множестве формул W.

3. Из п. 1, 2 с очевидностью следует справедливость утверждения 4.

Таким образом, в исчислении условно-зависимых предикатов доказательство выполнимости произвольной формулы B на заданном множестве дополнений $W$ при условии, что множество $W$ содержит дополнение, являющееся обобщением базового дополнения формулы B, сводится к означиванию переменных в формулах ${{T}_{1}}$ и $B$ объектами ПС. Затем проводится проверка условия, что в результате такого означивания формулы ${{T}_{1}}$ формируется ложное высказывание, а высказывание, полученное при означивании данными объектами переменных в формуле $B$, является истинным.

Пример 4. Допустим АИР необходимо определить, может ли он догнать в ПС движущийся объект. Для решения данной задачи робот формирует формулу $B$, включающую следующие дополнения: “Определить характеристики движущегося объекта” и “Догнать (АИР, ${{y}_{j}}({v}*,L*,\gamma *)$)”, где ${v}{\text{*}}$ – скорость движения, которую не должен превышать объект; $L{\text{*}}$ – максимально допустимое расстояние до объекта и $\gamma {\text{*}}$ – максимально допустимые значения полярных координат точки встречи с объектом.

Первое логическое дополнение формулы $B$ позволяет АИР оценить следующие фактические характеристики движущегося объекта: скорость движения ${v}$, расстояние до объекта L и значения полярных координат $\gamma $ точки встречи с объектом [33]. После подстановки данных характеристик движущегося объекта $o({v},L,\gamma )$ в базовое логическое дополнение “Догнать (АИР, ${{y}_{j}}({v}*,L*,\gamma *)$)” проверяется истинностное значение получаемого в результате высказывания. Данное высказывание является истинным, если для подвижного объекта ${{o}_{i}}({v},L,\gamma )$ выполняется условие $({v} \leqslant {v}*) \otimes (L \leqslant L*) \otimes (\gamma \leqslant \gamma *)$. В этом случае АИР принимает решение о целесообразности преследования движущегося объекта и реализует ТМП “Догнать объект”.

3. Метод проверки выполнимости формул в логике условно-зависимых предикатов. Сформулируем в общем виде метод проверки выполнимости формул на заданном множестве формул, определяющих текущую ситуацию ПС в логике условно-зависимых предикатов.

Пусть даны две произвольные n-местные формулы ${{D}_{1}} = {{P}_{1}}({{y}_{1}}(X_{1}^{1}),{{y}_{2}}(X_{2}^{1}), \ldots ,\;{{y}_{n}}(X_{n}^{1}))$ и D₂ = = ${{P}_{2}}({{y}_{1}}(X_{1}^{2}),{{y}_{2}}(X_{2}^{2}), \ldots ,{{y}_{n}}(X_{n}^{2}))$, такие, что осмысленные слова, биективно соответствующие предикатным символам ${{P}_{1}}$ и ${{P}_{2}}$, совпадают.

Определение 10. Формула ${{D}_{1}}$ является обобщением формулы ${{D}_{2}}$, если верно условие

где $ \oplus $ – означает, что для выполнения исходного условия достаточно справедливости либо левой, либо его правой части.

Отметим, что в этом случае означивание переменных в формуле D₂ допустимыми для этого объектами ПС приводит к порождению частных примеров для формулы D₁. Если же при произвольном означивании переменных в формуле D₁ в результате формируется ложное высказывание, то ложным будет и высказывание, полученное в результате такого же означивания переменных в формуле D₂.

Следует также отметить, что если верно условие

то формулы ${{D}_{1}}$ и ${{D}_{2}}$ – условно логически эквивалентные.

Пусть также даны две произвольные формулы:

Определение 11. Формула D₃ является обобщением формулы D₄, если выполняются следующие условия:

a) формулы D₃ и D₄ включают одинаковое количество предикатов;

б) для каждого предиката ${{P}_{i}}$, входящего в структуру формулы D₃, который содержит $n_{i}^{1}$ переменных, в структуре формулы D₄ имеется одноименный с ним предикат ${{P}_{j}}$, включающий $n_{j}^{2}$ переменных, для которого выполняется одно из следующих условий:

1) если $n_{j}^{2} < n_{i}^{1}$, то $\forall {{y}_{j}}(X_{j}^{2}) \in {{P}_{j}}\exists {{y}_{i}}(X_{i}^{1}) \in {{P}_{i}}[(X_{i}^{1} \subset X_{j}^{2}) \vee (X_{i}^{1} = X_{j}^{2})]$;

2) если $n_{j}^{2} = n_{i}^{1}$, то $\forall {{y}_{i}}(X_{i}^{1}) \in {{P}_{i}}\exists {{y}_{j}}(X_{j}^{2}) \in {{P}_{j}}[(X_{i}^{1} \subset X_{j}^{2}) \vee (X_{i}^{1} = X_{j}^{2})]$.

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

Входные переменные: $W$ – множество исходных посылок; $A = \{ a({{X}_{{ai}}})\} $, $i = \overline {1,{{m}_{1}}} $ – константы, используемые для означивания переменных в формулах ${{W}_{i}} \in W$ и B; B – формула, выполнимость которой требуется определить на множестве посылок W.

Промежуточные переменные: пара формул $\left\langle {{{W}_{i}},B} \right\rangle $, в которой дополнение ${{W}_{i}}$ является обобщением базового дополнения формулы B; $W_{i}^{*},B{\text{*}}$ – высказывания, полученные путем означивания переменных в формулах ${{W}_{i}} \in W$ и B константами $a({{X}_{{ai}}}) \in A$.

Выходные переменные: ложное либо истинное высказывание, полученное путем означивания переменных в формуле ${{T}_{1}} = \sim ({{W}_{1}}\& {{W}_{2}}\& ,\; \ldots ,\;\& {{W}_{i}}\& ,\; \ldots ,\;\& {{W}_{m}})\& B$ константами $a({{X}_{{ai}}}) \in A$, для которых формула В является истинной.

Метод.

1. Начало.

2. Проверить условие “в заданном множестве W содержится формула ${{W}_{i}} \in W$, которая является обобщением базового дополнения формулы B”: если условие выполняется, то перейти к п. 3, в противном случае перейти к п. 7.

3. Сформировать формулу ${{T}_{1}}$.

4. Сформировать означивание $I = \{ {{a}_{i}}({{X}_{{ai}}})\} $, $i = \overline {1,w} $, которое состоит из констант, удовлетворяющих требованиям всех переменных в формуле $B$, т.е. формула $B$ для означивания I является истинной.

5. Провести замену переменных ${{y}_{j}}({{X}_{j}})$ в формуле ${{T}_{1}}$ допустимыми константами ${{a}_{i}}({{X}_{{ai}}}) \in I$ и получить на этой основе высказывание ${{D}_{5}} = \sim (W_{1}^{*}\& W_{2}^{*}\& ,\; \ldots ,\;\& W_{i}^{*}\& ,\; \ldots ,\;\& W_{m}^{*})\& B{\text{*}}$.

6. Проверить условие “высказывание ${{D}_{5}}$ является ложным”: если да, то формула B выполнима на заданном множестве формул W, перейти к п. 8; в противном случае перейти к п. 7.

7. На исходном множестве формул W формула B является невыполнимой.

8. Конец.

Рассмотрим случай, когда множество формул W не содержит дополнение, которое является обобщением базового логического дополнения формулы B. Тогда, согласно п. 2 предложенного метода определения выполнимости формулы B, принимается решение о том, что она не выполнима на заданном множестве формул W.

Однако интеллектуальный решатель задач АИР при использовании предложенной модели представления знаний может быть наделен процедурами автоматической генерации формулы ${{D}_{i}}$, позволяющей обобщить имеющиеся в формулах $W$ сведения. Для этого проводится замена переменной ${{y}_{i}}({{X}_{i}})$ в формуле ${{W}_{i}} \in W$, у которой содержание предикатного символа совпадает с содержанием предикатного символа в базовом дополнении формулы B, на переменную ${{y}_{j}}({{X}_{j}})$, для которой выполняется условие $({{X}_{j}} \subset {{X}_{i}}) \otimes ({{X}_{j}} \subset {{X}_{B}})$, где ${{X}_{B}}$ – множество характеристик, определяющих переменную в базовом дополнении формулы $B$.

Следовательно, если будет выявлено, что формула B выполнима на множестве формул, в котором посылка D_i есть обобщение логического дополнения формулы ${{B}_{j}}({{y}_{j}}({{X}_{j}}),{{f}_{i}}({{X}_{{fi}}})) \in B$, то формула D_i  добавляется ко множеству исходных формул W, а формула В рассматривается как выполнимая на полученном таким образом множестве формул $W \cup {{D}_{i}}$.

Пример 5. Пусть у робота в процессе планирования целенаправленного поведения возникла необходимость установить справедливость утверждения – “Объект ПС $o({{X}_{j}})$ способен самостоятельно передвигаться”. Допустим, что в декларативной модели представления знаний АИР содержится логическое дополнение “Автомобили $({{X}_{i}})$ умеют перемещаться”, которое не является обобщением проверяемого утверждения. Тогда если в декларативной модели знаний робота имеется типовой элемент, определяющий в общем случае с помощью множества характеристик X_k все умеющие перемещаться объекты, то после замены переменной “Автомобили (X_i)” на переменную “Перемещающиеся объекты (X_k)” в результате получим дополнение “Объекты $({{X}_{k}})$ умеют перемещаться”. Данное логическое дополнение позволяет АИР установить, что объект $o({{X}_{j}})$ способен самостоятельно перемещаться, если для него выполняется условие ${{X}_{k}} \subseteq {{X}_{j}}$.

4. Концептуальные основы применения модели представления знаний для планирования целенаправленного поведения АИР. Предложенная модель представления и генерации новых знаний позволяет АИР автоматически сформировать план целенаправленного поведения в недоопределенной ПС следующим образом. Вначале на каждом шаге планирования поведения определяются различия между воспринимаемой в ПС ситуацией и ситуацией, требуемой для успешной отработки действий выбранной на данном шаге ТМП. Затем выявляются типовые микропрограммы поведения, содержащие действия, которые позволяют устранить данные различия. После этого автоматически формируются продукционные правила вывода, имеющие следующую структуру: “Если наблюдается различие $P_{i}^{*}$, то для его устранения необходимо реализовать действия ТМП F_i”. Используя полученные таким образом продукции, робот путем целенаправленного поиска в пространстве подзадач на основе условий и результатов отработки действий, содержащихся в выбранных типовых микропрограммах поведения, автоматически строит план поведения, который позволяет достичь ему заданной в процедурной форме цели [26].

Пример 6. Пусть в ПС не выполняются условия ${{P}_{i}}$, необходимые для успешной отработки действий ТМП ${{F}_{i}}$, выбранной на текущем шаге планирования поведения. Иными словами, между текущей и требуемой ситуацией ПС имеются различия, о чем свидетельствует то, что условия ${{P}_{i}}$ не соблюдаются в проблемной среде и их необходимо устранить для успешной отработки действий, входящих в структуру ТМП F_i.

В этом случае по содержанию условия ${{P}_{i}}$ АИР выбирает ТМП F_j, у которой входящие в ее структуру действия позволяют устранить соответствующее этому условию различие. На этой основе формируется продукционное правило вывода $\sim {\kern 1pt} {{P}_{i}}\& {{F}_{j}} \to {{S}_{i}}$, означающее, что отработка действий ТМП F_j позволяет преобразовать текущую ситуацию ПС в ситуацию ${{S}_{i}}$, в которой выполняется условие ${{P}_{i}}$.

Далее, если в ПС не выполняются условия P_j, необходимые для отработки действий, входящих в структуру ТМП F_j, то робот переходит на следующий шаг планирования поведения. На этом шаге по содержанию условий P_j выбирается следующая ТМП и т.д., пока не будет выявлена микропрограмма поведения, действия которой АИР может непосредственно отработать в текущей ситуации ПС. Сформированная таким образом цепочка действий позволяет устранить в ПС различия, препятствующие результативной отработке действий ТМП, соответствующей заданной цели поведения. При этом порядок отработки действий АИР в сформированном таким образом плане целенаправленного поведения определяется относительно последнего учтенного в нем различия.

Утверждение 5. Оценка $\beta $ сложности автоматического построения плана целенаправленного поведения АИР в недоопределенной ПС на основе предложенной модели представления знаний определяется следующими граничными значениями:

Доказательство 1. Примем в качестве показателя оценки сложности $\beta $, количество автоматически формируемых и применяемых продукционных правил вывода в процессе планирования целенаправленного поведения АИР.

2. Пусть после первого сформированного продукционного правила вывода для содержащегося в нем действия b₂ в ПС выполняются условия, необходимые для его успешной отработки. В этом случае план поведения АИР будет состоять из двух действий: ${{b}_{2}} \to {{b}_{1}} \to $ цель достигнута, где b₁ – действие, входящее в структуру дополнения второго типа, определяющего заданную цель поведения. Следовательно, минимальное значение оценки сложности вывода $\beta $ определяется выражением $\beta \geqslant 1$.

3. Допустим, что между текущей и требуемой ситуацией ПС на каждом i-м шаге планирования поведения наблюдается m_i различий, препятствующих отработке планируемых действий ${{b}_{i}}$, которые необходимо устранить (m_i – количество условий, которые должны выполняться в ПС для успешной отработки действий ${{b}_{i}}$ ТМП, выбранной на i-м шаге планирования). Тогда в процессе планирования целенаправленного поведения АИР необходимо будет сформировать не более $\sum\nolimits_{i = 1}^n {{{m}_{i}}} $ продукций для устранения всех наблюдаемых в ПС различий между воспринимаемыми и требуемыми для отработки действий ситуациями ПС, где n – общее количество шагов планирования. Следовательно, максимальное значение оценки $\beta $ может быть не более величины, равной $\sum\nolimits_{i = 1}^n {{{m}_{i}}} $.

4. Из п. 1–3 с очевидностью следует, что $1 \leqslant \beta \leqslant \sum\nolimits_{i - 1}^n {{{m}_{i}}} $.

Необходимо отметить, что для описания характеристик различных объектов и ситуаций ПС, переменных в формулах логики условно-зависимых предикатов, а также условий, выполнение которых требуется для результативной отработки планируемых АИР действий, можно использовать математический аппарат нечетких множеств. Это позволяет с высокой степенью обобщить задаваемые роботу знания. Например, все легкие и имеющие небольшие габаритные размеры объекты ПС, которые находятся близко, т.е. попадают в рабочую зону манипулятора АИР, могут быть захвачены его рабочим органом. Таким образом, при наличии аналогии между различными объектами и ситуациями ПС [28] АИР может использовать накопленный опыт поведения в новых условиях среды, аналогичных ранее встречавшимся ему условиям.

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

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

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

Дальнейшее развитие и применение предложенной модели представления знаний АИР связано с организацией на их основе инструментальной деятельности путем определения с помощью условно-зависимых предикатов в процессе планирования поведения таких объектов ПС, которые он может использовать в качестве инструментов для результативного выполнения определенных действий над другими объектами среды. Это позволяет АИР достигать заданные ему цели в сложных условиях реальной недоопределенной проблемной среды.