Планировщик (язык программирования) - Википедия - Planner (programming language)

Планировщик
РазработаноКарл Хьюитт
Впервые появился1969; 51 год назад (1969)

Планировщик (часто обозначаемый в публикациях как «ПЛАНИРОВЩИК», хотя это не акроним) - язык программирования разработано Карл Хьюитт в Массачусетский технологический институт, и впервые опубликовано в 1969 году. Сначала были реализованы подмножества, такие как Micro-Planner и Pico-Planner, а затем, по сути, весь язык был реализован как Поплер Джулианом Дэвисом из Эдинбургского университета в ПОП-2 язык программирования.[1] Производные, такие как QA4, Conniver, QLISP и Ether (см. метафора научного сообщества ) были важными инструментами в искусственный интеллект исследования 1970-х годов, которые повлияли на коммерческие разработки, такие как Инженерная среда знаний (KEE) и Инструмент автоматического мышления (ИЗОБРАЗИТЕЛЬНОЕ ИСКУССТВО).

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

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

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

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

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

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

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

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

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

Внедрение микропланировщика

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

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

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

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

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

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

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

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

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

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

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

Когда цель Q, Цель п1 и ... и цель пп

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

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

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

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

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

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

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

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

нет В.
В: - П.

Вышеупомянутая программа не сможет доказать нет п хотя это следует по правилам математической логики. Это иллюстрация того факта, что 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 г., Токио. Также в Искусственный интеллект в MIT, 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), «Искусственный интеллект в автоматизированном проектировании», САПР, Северная Голландия.
  • Маккарти, Джон; Абрахамс, Пол; Эдвардс, Дэниел; Харт, Тимоти; Левин, Михаил (1962), Руководство программиста на Лисп 1.5, MIT вычислительный центр и исследовательская лаборатория электроники.
  • Робинсон, Джон Алан (1965), "Машинно-ориентированная логика, основанная на принципе разрешения", Коммуникации ACM, Дои:10.1145/321250.321253.
  • Джерри Сассман и Терри Виноград. Справочное руководство по микропланированию Меморандум AI № 203, MIT Project MAC, июль 1970 г.
  • Терри Виноград. Процедуры как представление данных в компьютерной программе для понимания естественного языка MIT AI TR-235. Январь 1971 г.
  • Джерри Сассман, Терри Виноград и Юджин Чарняк. Справочное руководство Micro-Planner (обновление) AI Memo 203A, MIT AI Lab, декабрь 1971 г.
  • Карл Хьюитт. Описание и теоретический анализ (с использованием схем) планировщика, языка для доказательства теорем и манипулирования моделями в роботе Меморандум AI № 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), Структура планов и поведения, Эльзевир Северная Голландия.
  • Уолдингер, Ричард; Левитт, Карл (1974), Рассуждения о программах искусственного интеллекта.

внешняя ссылка