Системы искусственного интеллекта


Оценки сложности задачи планирования - часть 4


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

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

предельно конструктивная: обобщенная стандартная схема программы считается решением вычислительной задачи, если в любой интерпретации, удовлетворяющей всем ограничениям вычислительной модели, имеет место функция типа (XR Y), вычисляемая программой П, получающейся из обобщенной стандартной схемы программы соответствующей конкретизацией предикатных и функциональных символов.

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

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


 
 




- Начало -  - Назад -  - Вперед -