Методы решения задач

Функционирование многих ИС носит целеустремлён-ный характер (например, автономные интеллектуальные ро-боты). Такое функционирование сводится к решению зада-чи планирования пути достижения нужной цели из некото-рой фиксированной начальной ситуации. Результатом реше-ния задачи будет план действий – частично-упорядоченная совокупность действий. Такой план напоминает сценарий, где в качестве отношения между вершинами выступают от-ношения типа: "цель-подцель" "цель-действие", "действие-результат" и т.п. Любой путь в этом сценарии, ведущий от вершины, соответствующей текущей ситуации, в любую из целевых вершин, определяет план действий (разные пути к одной цели).

План действий ищется тогда, когда возникает нестан-дартная ситуация, для которой нет заранее известного набо-ра действий, приводящих к нужной цели. Все задачи пост-роения плана действий разбивают на два типа (соответ-ственно, две модели: планирование в пространстве состо-яний (SS-проблема) и планирование в пространстве задач (PR-проблема).

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

Среди обобщённых состояний выделены начальные состоя-ния (обычно одно) и конечные (целевые) состояния. SS-про-блема состоит в поиске пути, ведущего из начального состо-яния в одно из конечных.

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

При планировании в пространстве задач ситуация нес-колько иная. Пространство образуется в результате введе-ния на множестве задач отношения типа: "часть-целое", "задача-подзадача", "общий случай-частный случай" и т.п. Другими словами, пространство задач отражает декомпози-цию задач на подзадачи (цели на подцели). PR-проблема состоит в поиске декомпозиции исходной задачи на подза-дачи, приводящей к задачам, решение которых системе известно. Например, ИНТСИС известно, как вычисляются значения sin x и cos x для любого значения аргумента и как производится операция деления. Если необходимо вычис-лить c tg x, то решением PR-проблемы будет представление этой задачи в виде декомпозиции c tg x=cos x/sin x (кроме х=π/2+k π).

Date: 2016-07-25; view: 324; Нарушение авторских прав