Планировщик (язык программирования)

Планировщик

Парадигма	Мультипарадигмальность : логика , процедурность.
Разработано	Карл Хьюитт
Впервые появился	1969 год ( 1969 )
Основные реализации
Микропланер, Пико-Планнер, Поплер, ПИКО-ПЛАННЕР
Диалекты
QA4, Коннивер, QLISP, Эфир
Под влиянием
Пролог , Смолток

Planner (часто упоминаемый в публикациях как «PLANNER», хотя это не аббревиатура) — это язык программирования, разработанный Карлом Хьюиттом из Массачусетского технологического института и впервые опубликованный в 1969 году. Сначала были реализованы такие подмножества, как Micro-Planner и Pico-Planner, и затем, по сути, весь язык был реализован как Popler Джулианом Дэвисом из Эдинбургского университета на языке программирования POP-2 . Такие производные, как QA4, Conniver, QLISP и Ether (см. метафору научного сообщества ), были важными инструментами в исследованиях искусственного интеллекта в 1970-х годах, которые повлияли на коммерческие разработки, такие как среда разработки знаний (KEE) и инструмент автоматического рассуждения (ART).

Процедурный подход против логического подхода

Двумя основными парадигмами построения семантических программных систем были процедурная и логическая . Процессуальная парадигма была воплощена в Лисп в котором использовались рекурсивные процедуры, работающие со структурами списков.

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

Процедурное внедрение знаний

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

1. Преобразовал все в клаузальную форму. Преобразование всей информации в клаузальную форму проблематично, поскольку оно скрывает основную структуру информации.
2. Затем использовал резолюцию, чтобы попытаться получить доказательство от противного, добавив клаузальную форму отрицания доказываемой теоремы. Использование только разрешения в качестве правила вывода проблематично, поскольку оно скрывает основную структуру доказательств. Кроме того, использование доказательства от противного проблематично, поскольку аксиоматизации всех практических областей знания на практике противоречивы.

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

1. Прямая цепочка (ранее):

   Если утверждаете P, утверждаете Q

   Если утверждаете не Q, утверждайте не P

2. Обратная цепочка (следовательно)

   Если цель Q, цель P

   Если цель не P, цель не Q

В этом отношении на развитие Планировщика повлияли естественные дедуктивные логические системы (особенно система Фредерика Фитча [1952]).

Реализация микропланера

Подмножество под названием Micro-Planner было реализовано Джерри Сассманом , Юджином Чарняком и Терри Виноградом. и использовался в программе Винограда для понимания естественного языка SHRDLU , в работе Юджина Чарняка по пониманию историй, в работе Торна Маккарти по юридическим рассуждениям и в некоторых других проектах. Это вызвало большой ажиотаж в области искусственного интеллекта. Это также вызвало споры, поскольку предлагало альтернативу логическому подходу, который был одной из основных парадигм ИИ.

В SRI International Джефф Рулифсон, Ян Дерксен и Ричард Уолдингер разработали QA4 , основанный на конструкциях Planner, и представили контекстный механизм для обеспечения модульности выражений в базе данных. Эрл Сакердоти и Рене Ребо разработали QLISP, расширение QA4, встроенное в INTERLISP , обеспечивающее рассуждения, подобные Planner, встроенные в процедурный язык и развивающиеся в его богатой среде программирования. QLISP использовался Ричардом Вальдингером и Карлом Левиттом для проверки программ, Эрлом Сакердоти для планирования и мониторинга выполнения, Жан-Клодом Латомбом для автоматизированного проектирования, Нахумом Дершовицем для синтеза программ, Ричардом Файксом для дедуктивного поиска и Стивеном Коулсу за первую экспертную систему, которая определяла использование эконометрической модели.

Компьютеры были дорогими. У них был только один медленный процессор, а их память была очень маленькой по сравнению с сегодняшней. Поэтому Planner принял некоторые меры повышения эффективности, включая следующие:

• Возврат был принят для экономии использования времени и памяти за счет одновременной обработки и хранения только одной возможности при изучении альтернатив.
• Для экономии места и времени было принято предположение об уникальном имени, поскольку предполагалось, что разные имена относятся к разным объектам. Например, предполагалось, что такие названия, как Пекин (ранее название столицы КНР) и Пекин (нынешняя транслитерация столицы КНР), относятся к разным объектам.
• Предположение о закрытом мире можно реализовать путем условной проверки того, провалилась ли попытка доказать цель полностью. Позднее эта способность получила вводящее в заблуждение название « отрицание как неудача », поскольку для достижения цели G можно было сказать: «если пытаться добиться G полностью терпит неудачу, тогда утверждайте (Не G) ».

Происхождение Пролога

Джерри Сассман , Юджин Чарняк , Сеймур Паперт и Терри Виноград университет посетили Эдинбургский в 1971 году, распространяя новости о Micro-Planner и SHRDLU и ставя под сомнение подход к единообразной процедуре доказательства разрешения, который был основой Эдинбургских логистов. В Эдинбургском университете Брюс Андерсон внедрил подмножество Micro-Planner под названием PICO-PLANNER. и Джулиан Дэвис (1973) реализовали практически весь Planner.

По словам Дональда Маккензи, Пэт Хейс вспомнил о влиянии визита Пейперта в Эдинбург, который, искусственного интеллекта по словам коллеги Пейперта из Массачусетского технологического института, Карла Хьюитта, стал «сердцем Логикленда ». Пейперт красноречиво высказал свою критику подхода к разрешению споров, доминирующего в Эдинбурге: «…и по крайней мере один человек поднял палку и ушел из-за Пейперта».

Вышеупомянутые события вызвали напряженность среди логистов в Эдинбурге. Эта напряженность обострилась, когда Совет научных исследований Великобритании поручил сэру Джеймсу Лайтхиллу написать отчет о ситуации с исследованиями ИИ в Великобритании. [ Итоговый отчет Lighthill 1973 ; McCarthy 1973] был весьма критически настроен, хотя SHRDLU упоминался положительно.

Пэт Хейс посетил Стэнфорд, где узнал о Planner. Вернувшись в Эдинбург, он попытался убедить своего друга Боба Ковальски принять во внимание Planner в их совместной работе над автоматизированным доказательством теорем. «Доказательство разрешающих теорем было понижено из горячей темы до пережитка ошибочного прошлого. Боб Ковальски упорно верил в потенциал доказательства разрешающих теорем. Он тщательно изучал Planner». Ковальски [1988] заявляет: «Я помню, как пытался убедить Хьюитта, что Planner похож на SL-разрешение ». Но Planner был изобретен для целей процедурного внедрения знаний и представлял собой отказ от парадигмы единой процедуры доказательства резолюции. Кольмерауэр и Руссель так вспоминали свою реакцию, узнав о Планнере:

«Посещая съезд IJCAI в сентябре 71 года вместе с Жаном Трюделем, мы снова встретились с Робертом Ковальски и услышали лекцию Терри Винограда об обработке естественного языка. Тот факт, что он не использовал единый формализм, оставил нас в недоумении. Это было в то время. что мы узнали о существовании языка программирования Карла Хьюитта Planner. Отсутствие формализации этого языка, наше незнание Лиспа и, прежде всего, тот факт, что мы были абсолютно преданы логике, означали, что эта работа мало повлияла на наше дальнейшее развитие. исследовать."

Осенью 1972 года Филипп Руссель реализовал язык под названием Пролог (аббревиатура от PRO grammation en LOG ique – по-французски «логическое программирование»). Программы на Прологе обычно имеют следующую форму (что является частным случаем обратной цепочки в Planner):

Когда цель Q, цель P ₁ и ... и цель P _n

Пролог дублировал следующие аспекты Micro-Planner:

• Направленный на шаблон вызов процедур из целей ( т.е. обратная цепочка )
• Индексированная база данных процедур, ориентированных на шаблоны, и основных предложений.
• Отказ от парадигмы полноты, которая характеризовала предыдущие работы по доказательству теорем, и замена ее парадигмой процедурного внедрения знаний в языке программирования.

Пролог также дублировал следующие возможности Micro-Planner, которые были прагматически полезны для компьютеров той эпохи, поскольку экономили место и время:

• Структура управления возвратом
• Допущение об уникальном имени, согласно которому предполагается, что разные имена относятся к разным объектам, например , Пекин и Пекин считаются разными.
• Реификация неудачи. Способ, которым Planner установил, что что-то доказуемо, заключался в том, чтобы успешно попытаться достичь этого в качестве цели, а способ, которым он установил, что что-то недоказуемо, заключался в том, чтобы попытаться сделать это в качестве цели и явно потерпеть неудачу. Конечно, другая возможность состоит в том, что попытка доказать цель будет длиться вечно и никогда не принесет никакой пользы. Планировщик также имел (не выражение) конструкция, которая завершилась успешно, если выражение не удалось, что привело к появлению в Planner терминологии « Отрицание как неудача ».

Использование предположения и отрицания уникального имени в качестве отказа стало более сомнительным, когда внимание обратилось на открытые системы.

Следующие возможности Micro-Planner были исключены из Пролога:

• Управляемый шаблоном вызов процедурных планов из утверждений ( т . е. прямая цепочка )
• Логическое отрицание, например , (не (человеческий Сократ)) .

Пролог не включил отрицание отчасти потому, что оно поднимает проблемы реализации. Рассмотрим, например, если бы отрицание было включено в следующую программу на Прологе:

не К.

Вопрос: - П.

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

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

Ссылки

Библиография

• Брюс Андерсон. Документация для Школы искусственного интеллекта LIB PICO-PLANNER Эдинбургского университета. 1972 год
• Брюс Баумгарт. Альтернативное справочное руководство по Micro-Planner. Инструкция по эксплуатации Стэнфордской лаборатории искусственного интеллекта № 67, апрель 1972 г.
• Коулз, Стивен (1975), «Применение искусственного интеллекта для эвристического моделирования», 2-я Американо-японская компьютерная конференция .
• Файкс, Ричард (1975), Дедуктивные механизмы поиска для моделей описания состояния , IJCAI .
• Фитч, Фредерик (1952), Символическая логика: введение , Нью-Йорк: Рональд Пресс .
• Грин, Корделл (1969), «Применение доказательства теорем к решению проблем», IJCAI .
• Хьюитт, Карл (1969). «ПЛАННЕР: язык доказательства теорем на роботах». ИДЖКАИ . CiteSeerX   10.1.1.80.756 .
• Хьюитт, Карл (1971), «Процедурное внедрение знаний в планировщик», IJCAI .
• Карл Хьюитт. Журнал Byte «Вызов открытых систем». апрель 1985 г.
• Карл Хьюитт и Джефф Инман. «DAI между и между: от «интеллектуальных агентов» к науке об открытых системах» Транзакции IEEE по системам, человеку и кибернетике. Ноябрь/декабрь 1991 г.
• Карл Хьюитт и Гуль Ага. «Языки с защищенными предложениями Хорна: являются ли они дедуктивными и логическими?» Международная конференция по компьютерным системам пятого поколения, Омша, 1988. Токио. Также в «Искусственном интеллекте» Массачусетского технологического института , Vol. 2. Массачусетский технологический институт Пресс, 1991.
• Хьюитт, Карл (март 2006 г.), Повторный упадок логического программирования и почему оно будет перевоплощено - Что пошло не так и почему: уроки исследований и приложений искусственного интеллекта (PDF) , Технический отчет, AAAI Press, заархивировано из оригинала (PDF) 10 декабря 2017 г.
• Уильям Корнфельд и Карл Хьюитт. Метафора научного сообщества. Памятка AI MIT 641. Январь 1981 г.
• Билл Корнфельд и Карл Хьюитт. «Метафора научного сообщества» Транзакции IEEE по системам, человеку и кибернетике. Январь 1981 года.
• Билл Корнфельд. «Использование параллелизма для реализации эвристического поиска» IJCAI 1981.
• Билл Корнфельд. Докторская диссертация «Параллелизм в решении задач» MIT EECS. Август 1981 года.
• Билл Корнфельд. «Комбинаторно-имплозивные алгоритмы» CACM. 1982 год
• Роберт Ковальски. «Ограничения логики» Материалы четырнадцатой ежегодной конференции ACM по информатике 1986 года.
• Роберт Ковальски. «Ранние годы логического программирования», CACM, январь 1988 г.
• Латомбе, Жан-Клод (1976), «Искусственный интеллект в автоматизированном проектировании», CAD Systems , Северная Голландия .
• Маккарти, Джон; Абрахамс, Пол; Эдвардс, Дэниел; Харт, Тимоти; Левин, Майкл (1962), Руководство для программиста Lisp 1.5 , Вычислительный центр Массачусетского технологического института и исследовательская лаборатория электроники .
• Робинсон, Джон Алан (1965), «Машинно-ориентированная логика, основанная на принципе разрешения», Communications of ACM , 12 : 23–41, doi : 10.1145/321250.321253 .
• Джерри Сассман и Терри Виноград. Справочное руководство по микропланировщику AI Memo No, 203, MIT Project MAC, июль 1970 г.
• Терри Виноград. Процедуры как представление данных в компьютерной программе для понимания естественного языка MIT AI TR-235. Январь 1971 года.
• Джерри Сассман, Терри Виноград и Юджин Чарняк. Справочное руководство по микропланнеру (обновление) AI Memo 203A, MIT AI Lab, декабрь 1971 г.
• Карл Хьюитт. Описание и теоретический анализ (с использованием схем) Planner, языка для доказательства теорем и управления моделями в роботе с искусственным интеллектом. Памятка № 251, MIT Project MAC, апрель 1972 г.
• Евгений Чарняк. К модели понимания детских историй MIT AI TR-266. Декабрь 1972 года.
• Джулиан Дэвис. Справочное руководство Popler 1.6. Эдинбургский университет, Отчет ТПУ № 1, май 1973 г.
• Джефф Рулифсон, Ян Дерксен и Ричард Уолдингер. «QA4, Процедурное исчисление для интуитивного мышления», Техническая заметка 73 SRI AI Center, ноябрь 1973 г.
• Скотт Фалман. «Система планирования для задач по конструированию роботов» MIT AI TR-283. июнь 1973 г.
• Джеймс Лайтхилл. «Искусственный интеллект: общий обзор Искусственный интеллект: бумажный симпозиум». Совет научных исследований Великобритании. 1973.
• Джон Маккарти. «Обзор книги «Искусственный интеллект: общий обзор искусственного интеллекта: бумажный симпозиум». Совет научных исследований Великобритании. 1973.
• Роберт Ковальски «Логика предикатов как язык программирования», Памятка 70, Факультет искусственного интеллекта, Эдинбургский университет. 1973 год
• Пэт Хейс. Математические основы вычислений и дедукции в информатике: материалы симпозиума и летней школы, Штрбске Плесо, Высокие Татры, Чехословакия, 3–8 сентября 1973 г.
• Карл Хьюитт, Питер Бишоп и Ричард Стайгер. «Универсальный модульный формализм актеров для искусственного интеллекта» IJCAI 1973.
• Л. Торн Маккарти. «Размышления о TAXMAN: эксперимент по искусственному интеллекту и правовому рассуждению», Harvard Law Review. Том. 90, № 5, март 1977 г.
• Дрю МакДермотт и Джерри Сассман. Справочное руководство Conniver MIT AI Memo 259A. Январь 1974 года.
• Эрл Сакердоти и др., «QLISP — язык для интерактивной разработки сложных систем» AFIPS. 1976 год
• Сакердоти, Эрл (1977), Структура планов и поведения , Elsevier North-Holland .
• Уолдингер, Ричард; Левитт, Карл (1974), Рассуждения о программах искусственного интеллекта .

Внешние ссылки

• Отчет Алена Кольмерауэра и Филиппа Русселя о рождении Пролога в Wayback Machine в 1992 году (архивировано 27 июля 2003 г.)