Из Википедии, бесплатной энциклопедии
  (Перенаправлено с языка программирования Planner )
Перейти к навигации Перейти к поиску

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

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

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

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

Процедурное вложение знаний [ править ]

Планировщик был изобретен для процедурного встраивания знаний [Hewitt 1971] и являлся отказом от парадигмы процедуры единого доказательства разрешения [Robinson 1965], которая

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

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

  1. Прямая цепочка (ранее):
  • Если утверждать P, утверждать Q
    Если assert not Q, assert not P
  1. Обратная цепочка (как следствие)
  • Если цель Q, цель P
    Если гол не P, гол не Q

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

Реализация микропланировщика [ править ]

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

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

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

  • Отслеживание с возвратом [Golomb and Baumert 1965] было принято, чтобы сэкономить время и память, работая и сохраняя только одну возможность за раз при исследовании альтернатив.
  • Предположение об уникальном имени было принято для экономии места и времени, предполагая, что разные имена относятся к разным объектам. Например, предполагалось, что такие имена, как Пекин (предыдущее название столицы КНР) и Пекин (текущая транслитерация капитала КНР), относятся к разным объектам.
  • Замкнутый мир предположение может быть реализовано условно тестирования ли исчерпывающе удалась попытка доказать цель. Позже этой возможности было дано вводящее в заблуждение название « отрицание как неудача », потому что для цели G можно было сказать: «если попытка достичь G полностью терпит неудачу, тогда утверждать (не G) ».

Происхождение Пролога [ править ]

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

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

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

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

«На съезде IJCAI в сентябре 1971 года с Жаном Трюделем мы снова встретились с Робертом Ковальски и услышали лекцию Терри Винограда об обработке естественного языка. Тот факт, что он не использовал унифицированный формализм, оставил нас в недоумении. Это было в то время что мы узнали о существовании языка программирования Карла Хьюитта, Planner [Hewitt, 1969]. Отсутствие формализации этого языка, наше незнание Лиспа и, прежде всего, тот факт, что мы были абсолютно преданы логике, означало, что эта работа имела мало повлияло на наши последующие исследования ". [ Colmerauer and Roussel 1996]

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

Когда цель Q, цель P 1 и ... и цель P n

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

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

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

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

Использование допущения и отрицания уникального имени в качестве ошибки стало более сомнительным, когда внимание обратилось на открытые системы [Hewitt and de Jong 1983, Hewitt 1985, Hewitt and Inman 1991].

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

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

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

не Q.
В: - П.

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

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

См. Также [ править ]

  • Логическое программирование
  • Пролог

Ссылки [ править ]

  1. ^ Карл Хьюитт Средняя история логического программирования: разрешение, планировщик, пролог и японский проект пятого поколения ArXiv 2009. arXiv : 0904.3036

Библиография [ править ]

  • Брюс Андерсон. Документация для школы искусственного интеллекта LIB PICO-PLANNER, Эдинбургский университет. 1972 г.
  • Брюс Баумгарт. Альтернативное справочное руководство Micro-Planner Операционная записка Стэнфордской лаборатории искусственного интеллекта № 67, апрель 1972 г.
  • Коулз, Стивен (1975), «Применение искусственного интеллекта для эвристического моделирования», 2-я американско-японская компьютерная конференция.
  • Файкс, Ричард (1975), Механизмы дедуктивного поиска для моделей описания состояний , IJCAI.
  • Фитч, Фредерик (1952), Символическая логика: введение , Нью-Йорк: Рональд Пресс.
  • Грин, Корделл (1969), "Применение доказательства теорем к решению задач", IJCAI.
  • Хьюитт, Карл (1969). «ПЛАНИРОВЩИК: язык для доказательства теорем в роботах». IJCAI . CiteSeerX  10.1.1.80.756 .
  • Хьюитт, Карл (1971), «Процедурное встраивание знаний в планировщик», IJCAI.
  • Карл Хьюитт. "Вызов открытых систем" Byte Magazine. Апрель 1985 г.
  • Карл Хьюитт и Джефф Инман. "DAI Betwixt and Between: From 'Intelligent Agents' to Open Systems Science" IEEE Transactions on Systems, Man, and Cybernetics. Ноябрь / декабрь 1991 г.
  • Карл Хьюитт и Гул Ага. «Языки с оговорками Сторожевого Рога: являются ли они дедуктивными и логическими?» Международная конференция по компьютерным системам пятого поколения, Омша, 1988 г., Токио. Также в искусственном интеллекте в Массачусетском технологическом институте , Vol. 2. MIT Press 1991.
  • Хьюитт, Карл (март 2006 г.), Неоднократная кончина логического программирования и причины его реинкарнации - Что пошло не так и почему: уроки исследований и приложений искусственного интеллекта (PDF) , Технический отчет, AAAI Press, заархивировано из оригинала (PDF) на 2017-12-10.
  • Уильям Корнфельд и Карл Хьюитт. Метафора научного сообщества MIT AI Memo 641. Январь 1981.
  • Билл Корнфельд и Карл Хьюитт. "Метафора научного сообщества" IEEE Transactions по системам, человеку и кибернетике. Январь 1981 г.
  • Билл Корнфельд. «Использование параллелизма для реализации эвристического поиска» IJCAI 1981.
  • Билл Корнфельд. "Параллелизм в решении проблем" Докторская диссертация MIT EECS. Август 1981 г.
  • Билл Корнфельд. "Комбинаторно имплозивные алгоритмы" CACM. 1982 г.
  • Роберт Ковальски. "Ограничения логики" Труды четырнадцатой ежегодной конференции ACM 1986 года по информатике.
  • Роберт Ковальски. "Первые годы логического программирования" CACM, январь 1988 г.
  • Латомбе, Жан-Клод (1976), «Искусственный интеллект в автоматизированном проектировании», CAD Systems , Северная Голландия.
  • Маккарти, Джон; Абрахамс, Пол; Эдвардс, Дэниел; Харт, Тимоти; Левин, Майкл (1962), Руководство программиста Lisp 1.5 , Вычислительный центр Массачусетского технологического института и Исследовательская лаборатория электроники.
  • Робинсон, Джон Алан (1965), «машинно-ориентированная логика , основанная на принципе Resolution», коммуникаций АСМ , DOI : 10,1145 / 321250,321253.
  • Джерри Сассман и Терри Виноград. Справочное руководство по микропланированию AI Memo No. 203, MIT Project MAC, июль 1970.
  • Терри Виноград. Процедуры как представление данных в компьютерной программе для понимания естественного языка MIT AI TR-235. Январь 1971 г.
  • Джерри Сассман, Терри Виноград и Юджин Чарняк. Справочное руководство Micro-Planner (обновление) AI Memo 203A, MIT AI Lab, декабрь 1971 г.
  • Карл Хьюитт. Описание и теоретический анализ (с использованием схем) планировщика, языка для доказательства теорем и манипулирования моделями в записке ИИ робота № 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. Vol. 90, No. 5, март 1977 г.
  • Дрю Макдермотт и Джерри Сассман. Справочное руководство Conniver MIT AI Memo 259A. Январь 1974 г.
  • Эрл Сакердоти и др., "QLISP - язык для интерактивной разработки сложных систем" AFIPS. 1976 г.
  • Сакердоти, Эрл (1977), Структура планов и поведения , Elsevier North-Holland.
  • Уолдингер, Ричард; Левитт, Карл (1974), Рассуждения о программах искусственного интеллекта.

Внешние ссылки [ править ]

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