Программирование набора ответов - Answer set programming - Wikipedia

Программирование набора ответов (ASP) является формой декларативное программирование ориентированы на сложные (в первую очередь NP-жесткий ) проблемы с поиском. Он основан на стабильная модель (набор ответов) семантика логическое программирование. В ASP проблемы поиска сводятся к вычислению стабильных моделей и решатели наборов ответов- программы генерации устойчивых моделей - используются для поиска. Вычислительный процесс, используемый при разработке многих решателей наборов ответов, является усовершенствованием Алгоритм DPLL и, в принципе, всегда заканчивается (в отличие от Пролог оценка запроса, что может привести к бесконечный цикл ).

В более общем смысле, ASP включает все приложения наборов ответов для представление знаний^[1]^[2] и использование оценки запросов в стиле Пролога для решения проблем, возникающих в этих приложениях.

История

В планирование метод, предложенный в 1993 г. Димопулосом, Небелем и Кёлером^[3] это ранний пример программирования набора ответов. Их подход основан на соотношении планов и стабильных моделей.^[4] Сойнинен и Ниемеля^[5] применил то, что теперь известно как программирование наборов ответов, к проблеме конфигурации продукта. Использование решателей наборов ответов для поиска было определено как новая парадигма программирования. Марек и Трушчинский в статье, опубликованной в 1999 г. в 25-летней перспективе парадигмы логического программирования. ^[6] и в [Niemelä 1999].^[7] Действительно, новую терминологию «набор ответов» вместо «стабильной модели» впервые предложил Лифшиц.^[8] в статье, вышедшей в том же ретроспективном томе, что и статья Марека-Трущинского.

Набор ответов язык программирования AnsProlog

Lparse это имя программы, которая изначально была создана как заземление инструмент (интерфейс) для решателя наборов ответов смодели. Язык, который принимает Lparse, теперь обычно называется AnsProlog *,^[9] Короче для Программирование набора ответов в логике.^[10] Теперь он таким же образом используется во многих других решателях наборов ответов, включая Ассат, застежка, cmodels, gNt, nomore ++ и pbmodels. (dlv это исключение; синтаксис программ ASP, написанных для dlv, несколько отличается.)

Программа AnsProlog состоит из правил вида

<голова> :- <тело> .

Символ :- ("если") отбрасывается, если <body> пусто; такие правила называются факты. Самый простой вид правил Lparse: правила с ограничениями.

Еще одна полезная конструкция, включенная в этот язык, - выбор. Например, правило выбора

{п,q,р}.

говорит: выбирайте произвольно, какой из атомов ${ displaystyle p, q, r}$ включить в стабильную модель. Программа lparse, содержащая это правило выбора и никаких других правил, имеет 8 стабильных моделей - произвольные подмножества ${ Displaystyle {п, д, г }}$ . Определение стабильной модели было обобщено на программы с правилами выбора.^[11] Правила выбора можно рассматривать также как аббревиатуры для пропозициональные формулы в семантике стабильной модели.^[12] Например, приведенное выше правило выбора можно рассматривать как сокращение для соединения трех "исключенный средний формулы:

{ Displaystyle (п лор нег р) земля (д лор нег q) земля (г лор нег р).}

Язык lparse позволяет нам также писать "ограниченные" правила выбора, такие как

1{п,q,р}2.

Это правило гласит: выберите хотя бы 1 из атомов ${ displaystyle p, q, r}$ , но не более 2. Смысл этого правила в семантике стабильной модели выражается пропозициональная формула

{ Displaystyle (п лор нег р) земля (д лор нег q) земля (г лор нег р)}

{ displaystyle land , (p lor q lor r) land neg (p land q land r).}

Границы мощности также могут использоваться в теле правила, например:

:- 2{п,q,р}.

Добавление этого ограничения в программу Lparse удаляет стабильные модели, содержащие как минимум 2 атома ${ displaystyle p, q, r}$ . Смысл этого правила может быть представлен пропозициональной формулой

{ Displaystyle neg ((п земля q) лор (п земля г) лор (д земля р)).}

Переменные (с заглавной буквы, как в Пролог ) используются в Lparse для сокращения наборов правил, которые следуют одному и тому же шаблону, а также для сокращения наборов атомов в одном правиле. Например, программа Lparse

п(а). п(б). п(c).q(Икс) :- п(Икс), Икс!=а.

имеет то же значение, что и

п(а). п(б). п(c).q(б). q(c).

Программа

п(а). п(б). п(c).{q(Икс):-п(Икс)}2.

сокращение для

п(а). п(б). п(c).{q(а),q(б),q(c)}2.

А классифицировать имеет вид:

(Начните..конец)

где начало и конец - арифметические выражения с постоянным значением. Диапазон - это сокращенное обозначение, которое в основном используется для определения числовых доменов совместимым способом. Например, факт

а(1..3).

это ярлык для

а(1). а(2). а(3).

Диапазоны также могут использоваться в телах правил с той же семантикой.

А условный буквальный имеет вид:

п(Икс):q(Икс)

Если расширение q есть {q (a1); q (a2); ...; q (aN)}, указанное выше условие семантически эквивалентно записи p (a1), p (a2), ..., p (aN) вместо условия. Например,

q(1..2).а :- 1 {п(Икс):q(Икс)}.

это сокращение для

q(1). q(2).а :- 1 {п(1), п(2)}.

Создание стабильных моделей

Чтобы найти стабильную модель программы Lparse, хранящуюся в файле $ {имя файла} мы используем команду

% lparse ${имя файла} | смодели

Вариант 0 дает команду смоделам найти все стабильные модели программы. Например, если файл тест содержит правила

1{п,q,р}2.s :- нет п.

тогда команда производит вывод

% lparse тест | смодели 0Ответ: 1Стабильная модель: q p Ответ: 2Стабильная модель: p Ответ: 3Стабильная модель: r p Ответ: 4Стабильная модель: q s Ответ: 5Стабильная модель: r s Ответ: 6Стабильная модель: r q s

Примеры программ ASP

Раскраска графика

An ${ displaystyle n}$ -раскраска из график ${ displaystyle G = left langle V, E right rangle}$ это функция ${ displaystyle mathrm {color}: от V to {1, dots, n }}$ такой, что ${ Displaystyle mathrm {цвет} (х) neq mathrm {цвет} (у)}$ для каждой пары смежных вершин ${ displaystyle (x, y) in E}$ . Мы хотели бы использовать ASP, чтобы найти ${ displaystyle n}$ -раскрашивание заданного графа (или определение того, что его не существует).

Это можно сделать с помощью следующей программы Lparse:

c(1..п).                                           1 {цвет(Икс,я) : c(я)} 1 :- v(Икс).             :- цвет(Икс,я), цвет(Y,я), е(Икс,Y), c(я).

Строка 1 определяет числа ${ Displaystyle 1, точки, п}$ быть цветами. Согласно правилу выбора в строке 2, уникальный цвет ${ displaystyle i}$ должна быть назначена каждой вершине ${ displaystyle x}$ . Ограничение в строке 3 запрещает назначать один и тот же цвет вершинам. ${ displaystyle x}$ и ${ displaystyle y}$ если есть ребро, соединяющее их.

Если мы объединим этот файл с определением ${ displaystyle G}$ , Такие как

v(1..100). % 1, ..., 100 - вершиные(1,55). % есть преимущество от 1 до 55. . .

и запускаем на нем смоделы с числовым значением ${ displaystyle n}$ указывается в командной строке, то атомы формы ${ Displaystyle mathrm {цвет} ( точки, точки)}$ на выходе смоделей будет представлять ${ displaystyle n}$ -крашивание ${ displaystyle G}$ .

Программа в этом примере иллюстрирует организацию «генерации и тестирования», которая часто встречается в простых программах ASP. Правило выбора описывает набор «потенциальных решений» - простое надмножество множества решений данной поисковой задачи. За ним следует ограничение, которое устраняет все возможные решения, которые не являются приемлемыми. Однако процесс поиска, используемый смоделями и другими решателями наборов ответов, не основан на методом проб и ошибок.

Большая клика

А клика в графе - это множество попарно смежных вершин. Следующая программа lparse находит клику размером ${ displaystyle geq n}$ в заданном графе или определяет, что его не существует:

п {в(Икс) : v(Икс)}.:- в(Икс), в(Y), v(Икс), v(Y), Икс!=Y, нет е(Икс,Y), нет е(Y,Икс).

Это еще один пример организации «генерировать и тестировать». Правило выбора в строке 1 «генерирует» все наборы, состоящие из ${ displaystyle geq n}$ вершины. Ограничение в строке 2 «отсеивает» множества, не являющиеся кликами.

Гамильтонов цикл

А Гамильтонов цикл в ориентированный граф это цикл который проходит через каждую вершину графа ровно один раз. Следующая программа Lparse может использоваться для поиска гамильтонова цикла в заданном ориентированном графе, если он существует; мы предполагаем, что 0 - одна из вершин.

{в(Икс,Y)} :- е(Икс,Y).:- 2 {в(Икс,Y) : е(Икс,Y)}, v(Икс).:- 2 {в(Икс,Y) : е(Икс,Y)}, v(Y).р(Икс) :- в(0,Икс), v(Икс).р(Y) :- р(Икс), в(Икс,Y), е(Икс,Y).:- нет р(Икс), v(Икс).

Правило выбора в строке 1 «генерирует» все подмножества набора ребер. Эти три ограничения «отсеивают» подмножества, не являющиеся гамильтоновыми циклами. Последний из них использует вспомогательный предикат ${ Displaystyle г (х)}$ (" ${ displaystyle x}$ достижимо из 0 "), чтобы запретить вершины, которые не удовлетворяют этому условию. Этот предикат определяется рекурсивно в строках 4 и 5.

Эта программа является примером более общей организации «генерировать, определять и тестировать»: она включает определение вспомогательного предиката, который помогает нам исключить все «плохие» потенциальные решения.

Разбор зависимостей

В обработка естественного языка, анализ на основе зависимостей можно сформулировать как проблему ASP.^[13]Следующий код анализирует латинское предложение «Puella pulchra in villa linguam latinam discit», «красивая девушка изучает латынь на вилле». Синтаксическое дерево выражается дуга предикаты, которые представляют зависимости между словами предложения. Вычисляемая структура представляет собой линейно упорядоченное корневое дерево.

% ********** предложение ввода **********слово(1, Puella). слово(2, Pulchra). слово(3, в). слово(4, вилла). слово(5, лингвам). слово(6, латыни). слово(7, дискит).% ********** лексикон **********1{ узел(Икс, attr(пулчер, а, женщина, ном, sg));   узел(Икс, attr(пулчер, а, женщина, ном, sg)) }1 :- слово(Икс, Pulchra).узел(Икс, attr(латинский, а, женщина, соотв, sg)) :- слово(Икс, латыни).1{ узел(Икс, attr(Puella, п, женщина, ном, sg));   узел(Икс, attr(Puella, п, женщина, abl, sg)) }1 :- слово(Икс, Puella).1{ узел(Икс, attr(вилла, п, женщина, ном, sg));   узел(Икс, attr(вилла, п, женщина, abl, sg)) }1 :- слово(Икс, вилла).узел(Икс, attr(лингвам, п, женщина, соотв, sg)) :- слово(Икс, лингвам).узел(Икс, attr(различать, v, прес, 3, sg)) :- слово(Икс, дискит).узел(Икс, attr(в, п)) :- слово(Икс, в).% ********** синтаксические правила **********0{ дуга(Икс, Y, subj) }1 :- узел(Икс, attr(_, v, _, 3, sg)), узел(Y, attr(_, п, _, ном, sg)).0{ дуга(Икс, Y, добдж) }1 :- узел(Икс, attr(_, v, _, 3, sg)), узел(Y, attr(_, п, _, соотв, sg)).0{ дуга(Икс, Y, attr) }1 :- узел(Икс, attr(_, п, Пол, Дело, Число)), узел(Y, attr(_, а, Пол, Дело, Число)).0{ дуга(Икс, Y, подготовка) }1 :- узел(Икс, attr(_, п)), узел(Y, attr(_, п, _, abl, _)), Икс < Y.0{ дуга(Икс, Y, нарекать) }1 :- узел(Икс, attr(_, v, _, _, _)), узел(Y, attr(_, п)), нет лист(Y).% ********** гарантия точности графика **********1{ корень(Икс):узел(Икс, _) }1.:- дуга(Икс, Z, _), дуга(Y, Z, _), Икс != Y.:- дуга(Икс, Y, L1), дуга(Икс, Y, L2), L1 != L2.дорожка(Икс, Y) :- дуга(Икс, Y, _).дорожка(Икс, Z) :- дуга(Икс, Y, _), дорожка(Y, Z).:- дорожка(Икс, Икс).:- корень(Икс), узел(Y, _), Икс != Y, нет дорожка(Икс, Y).лист(Икс) :- узел(Икс, _), нет дуга(Икс, _, _).

Стандартизация языков и конкуренция ASP

Рабочая группа по стандартизации ASP разработала стандартную языковую спецификацию, получившую название ASP-Core-2,^[14] к которому сходятся последние системы ASP. ASP-Core-2 - это эталонный язык для соревнований по программированию набора ответов, на котором решатели ASP периодически проходят тестирование по ряду эталонных задач.

Сравнение реализаций

Ранние системы, такие как Smodels, использовали возврат найти решения. Поскольку теория и практика Булевы решатели SAT В дальнейшем ряд решателей ASP был построен на основе решателей SAT, включая ASSAT и Cmodels. Они преобразовали формулу ASP в предложения SAT, применили решатель SAT, а затем преобразовали решения обратно в форму ASP. Более поздние системы, такие как Clasp, используют гибридный подход, используя алгоритмы, основанные на конфликтах, вдохновленные SAT, без полного преобразования в форму логической логики. Эти подходы позволяют значительно улучшить производительность, часто на порядок, по сравнению с более ранними алгоритмами поиска с возвратом.

В Potassco проект выступает в качестве зонтика для многих из перечисленных ниже систем, включая застежка, системы заземления (гринго), инкрементальные системы (иклинго), решатели ограничений (Clingcon), язык действия компиляторам ASP (коала), распределенные реализации MPI (застежка), и много других.

Большинство систем поддерживают переменные, но только косвенно, путем принудительного заземления, с помощью системы заземления, такой как Lparse или же гринго как передняя часть. Необходимость заземления может вызвать комбинаторный взрыв статей; таким образом, системы, которые выполняют заземление «на лету», могут иметь преимущество.

Платформа			Функции					Механика
Имя	Операционные системы	Лицензия	Переменные	Функциональные символы	Явные множества	Явные списки	Дизъюнктивная (правила выбора) поддержка
ASPeRiX	Linux	GPL	да				Нет	заземление на лету
АССАТ	Солярис	Бесплатное ПО						На основе SAT-решателя
Решатель набора ответов застежки	Linux, macOS, Windows	Лицензия MIT	Да, в Clingo	да	Нет	Нет	да	инкрементальный, вдохновленный SAT-решателем (неэффективный, управляемый конфликтами)
Cmodels	Linux, Солярис	GPL	Требуется заземление				да	инкрементальный, вдохновленный SAT-решателем (неэффективный, управляемый конфликтами)
delSAT	Linux, macOS, Windows (Виртуальная машина Java )	Лицензия MIT	Требуется заземление				да	Вдохновленный SAT-решателем (нет, конфликтный). Поддерживает решение вероятностных задач и выборку ответов
DLV	Linux, macOS, Windows^[15]	бесплатно для академических и некоммерческих образовательных целей, а также для некоммерческих организаций^[15]	да	да	Нет	Нет	да	не совместим с Lparse
DLV-Комплекс	Linux, macOS, Windows	GPL		да	да	да	да	построен на вершине DLV - не совместим с Lparse
GnT	Linux	GPL	Требуется заземление				да	построен на смоделах
Jekejeke	Linux, macOS, Windows (Виртуальная машина Java )	Проприетарный	да	да			да	Вариант DPLL через безопасную прямую цепочку
nomore ++	Linux	GPL						комбинированный литерал + основанный на правилах
Утконос	Linux, Солярис, Windows	GPL						распределенный, многопоточный nomore ++, смодели
Pbmodels	Linux	?						псевдобулево на основе решателя
Смоделы	Linux, macOS, Windows	GPL	Требуется заземление	Нет	Нет	Нет	Нет
Смодельс-CC	Linux	?	Требуется заземление					На базе SAT-решателя; смодели с оговорками о конфликте
Как дела	Linux	?						На основе SAT-решателя

Смотрите также

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

[1] Барал, Читта (2003). Представление знаний, аргументация и декларативное решение проблем. Издательство Кембриджского университета. ISBN 978-0-521-81802-5.

[2] Гельфонд, Майкл (2008). "Наборы ответов". В ван Хармелен, Франк; Лифшиц, Владимир; Портер, Брюс (ред.). Справочник по представлению знаний. Эльзевир. С. 285–316. ISBN 978-0-08-055702-1. как PDF В архиве 2016-03-03 в Wayback Machine

[3] Dimopoulos, Y .; Небель, Б.; Кёлер, Дж. (1997). «Задачи планирования кодирования в программах с немонотонной логикой». In Steel, Сэм; Алами, Рашид (ред.). Последние достижения в планировании искусственного интеллекта: 4-я Европейская конференция по планированию, ECP'97, Тулуза, Франция, 24–26 сентября 1997 г., Материалы. Конспект лекций по информатике: конспект лекций по искусственному интеллекту. 1348. Springer. С. 273–285. ISBN 978-3-540-63912-1. как постскриптум

[4] Субрахманян, В.С .; Заниоло, К. (1995). «Связь стабильных моделей и областей планирования ИИ». В Стерлинге, Леон (ред.). Логическое программирование: Материалы Двенадцатой Международной конференции по логическому программированию. MIT Press. С. 233–247. ISBN 978-0-262-69177-2. как постскриптум

[5] Сойнинен, Т .; Ниемеля, И. (1998), Формализация знаний о конфигурации с помощью правил с вариантами выбора (Постскриптум), Лаборатория науки обработки информации, Хельсинкский технологический университет

[6] Марек, В .; Трушчинский, М. (1999). «Стабильные модели и альтернативная парадигма логического программирования». В Apt, Кшиштоф Р. (ред.). Парадигма логического программирования: 25-летняя перспектива (PDF). Springer. С. 169–181. arXiv:cs / 9809032. ISBN 978-3-540-65463-6.

[7] Ниемеля, И. (1999). «Логические программы со стабильной семантикой модели как парадигма программирования в ограничениях» (Постскриптум, сжатый). Анналы математики и искусственного интеллекта. 25 (3/4): 241–273. Дои:10.1023 / А: 1018930122475.

[8] Лифшиц В. (1999). «Языки действий, наборы ответов и планирование». Цитировать журнал требует | журнал = (помощь) В Апт 1999 г., стр. 357–374

[9] Крик, Том (2009). Супероптимизация: создание оптимального кода с помощью программирования набора ответов (PDF) (Кандидат наук.). Университет Бата. Дело 20352. Архивировано с оригинал (PDF) на 2016-03-04. Получено 2011-05-27.

[10] Рохелио Давила. «Анспролог, обзор» (Силовая установка).

[11] Niemelä, I .; Simons, P .; Сойненен, Т. (2000). «Стабильная модельная семантика правил весовых ограничений». В Гельфонде, Михаил; Леоне, Николь; Пфайфер, Джеральд (ред.). Логическое программирование и немонотонные рассуждения: 5-я международная конференция, LPNMR '99, Эль-Пасо, Техас, США, 2–4 декабря 1999 г. Труды. Конспект лекций по информатике: конспект лекций по искусственному интеллекту. 1730. Springer. С. 317–331. ISBN 978-3-540-66749-0. как постскриптум

[12] Ferraris, P .; Лифшиц, В. (январь 2005 г.). «Ограничения веса как вложенные выражения». Теория и практика логического программирования. 5 (1–2): 45–74. arXiv:cs / 0312045. Дои:10.1017 / S1471068403001923. как постскриптум

[13] «Разбор зависимостей». Архивировано из оригинал на 2015-04-15. Получено 2015-04-15.

[14] «Спецификация языка ввода ASP-Core-2» (PDF). Получено 14 мая 2018.

[dlvsystem.com-15] а ^б "Страница компании DLV System". DLVSYSTEM s.r.l. Получено 16 ноября 2011.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]