Answer Set Programming¶

Answer Set Programming (ASP, программирование наборами ответов) — это формальная парадигма декларативного программирования, основанная на логическом представлении знаний и вычислении стабильных моделей (наборов ответов) для заданной логической программы. ASP относится к области представления знаний и рассуждений (Knowledge Representation and Reasoning, KRR) и используется для решения сложных комбинаторных задач, задач планирования, конфигурации и диагностики.

¶История

Истоки ASP лежат в работах по логическому программированию и неклассическим логикам. В конце 1980-х годов были разработаны концепции семантики стабильных моделей (Gelfond, Lifschitz, 1988) и семантики обоснованного отрицания (well-founded semantics). В 1999 году группа исследователей (включая Илька Ниемеля, Патрика Симмонса и Томаса Эйтера) предложила термин «Answer Set Programming» и разработала первые эффективные решатели (solver), такие как SMODELS и DLV. В 2000-х годах ASP получила широкое распространение в академической среде, появились стандартизированные языки (например, ASP-Core-2) и международные соревнования решателей (ASP Competition). В 2010-х годах ASP стала применяться в промышленных задачах, включая биоинформатику, робототехнику и автоматическое планирование.

¶Основные понятия

¶Логическая программа

ASP-программа состоит из набора правил вида: head :- body. где head — атом (или пусто), а body — конъюнкция литералов (атомов или их отрицаний). Правило без тела называется фактом. Правило без головы называется ограничением (constraint) и означает, что тело не может быть истинным.

¶Набор ответов

Набор ответов (answer set) — это минимальная модель программы, удовлетворяющая правилам и семантике стабильных моделей. Интуитивно, это непротиворечивое множество атомов, которое может быть выведено из программы при условии, что все правила, тело которых истинно, имеют голову в этом множестве. Если программа имеет несколько наборов ответов, каждый из них представляет одно из возможных решений задачи.

¶Отрицание

ASP использует два типа отрицания:

• Классическое отрицание (not): «не доказано, что истинно». Означает, что атом не входит в набор ответов.
• Сильное отрицание (-): «доказано, что ложно». Используется для явного указания ложности атома.

¶Язык и синтаксис

ASP-программы пишутся на языках, близких к Прологу, но с дополнительными конструкциями. Основные элементы:

• Факты: a. (атом a истинен).
• Правила: b :- a1, a2, not a3. (если a1 и a2 истинны, а a3 не доказан, то b истинно).
• Ограничения: :- a, b. (не может быть, чтобы a и b были одновременно истинны).
• Выбор: {a; b; c} 1. (ровно один из атомов a, b, c истинен).
• Агрегации: #count{X: p(X)} = N. (количество атомов, удовлетворяющих условию, равно N).

Стандартный синтаксис определён в спецификации ASP-Core-2 (2013).

¶Решатели (Solvers)

ASP-программа не выполняется, а решается — то есть находится один или все наборы ответов. Для этого используются специализированные решатели:

• CLINGO (разработчик — Потсдамский университет, Германия) — один из самых популярных, включает язык ASP-Core-2 и расширения (например, многозначные предикаты).
• DLV (разработчик — Университет Калабрии, Италия) — один из первых, поддерживает сильное отрицание и встроенные предикаты.
• WASP (разработчик — Университет Калабрии) — современный решатель с оптимизациями.
• SMODELS (разработчик — Хельсинкский университет, Финляндия) — исторически первый, но менее используемый сегодня.

Решатели обычно работают в два этапа: сначала программа преобразуется в эквивалентную булеву формулу (SAT), а затем применяется SAT-решатель (например, MiniSAT) или специализированный алгоритм поиска.

¶Применение

¶Комбинаторная оптимизация

ASP широко применяется для решения NP-трудных задач, таких как:

• Задача о вершинном покрытии: найти минимальное множество вершин графа, покрывающих все рёбра.
• Задача о раскраске графа: определить, можно ли раскрасить вершины графа в заданное число цветов так, чтобы смежные вершины имели разные цвета.
• Задача о выполнимости КНФ: проверить, существует ли набор значений переменных, делающий формулу истинной.

¶Планирование и робототехника

ASP используется для автоматического планирования действий роботов и автономных систем. Например, программа может описать начальное состояние, действия и цели, а решатель найдёт последовательность действий, ведущую к цели. Примеры: планирование маршрута, управление манипуляторами, координация роя дронов.

¶Биоинформатика

В биоинформатике ASP применяется для:

• Анализа генетических сетей: моделирование регуляторных взаимодействий.
• Предсказания структуры белков: поиск стабильных конформаций.
• Филогенетики: реконструкция эволюционных деревьев.

¶Конфигурация и диагностика

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

¶Игры и головоломки

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

¶Пример: задача о раскраске графа

Рассмотрим простой граф с тремя вершинами a, b, c и рёбрами a-b, b-c, c-a. Требуется раскрасить вершины в два цвета (красный и синий) так, чтобы смежные вершины имели разные цвета.

ASP-программа: ``` % Цвета: 1 — красный, 2 — синий color(1). color(2).

% Каждая вершина должна иметь ровно один цвет {color(X, C) : color(C)} = 1 :- vertex(X).

% Смежные вершины не могут иметь одинаковый цвет :- vertex(X), vertex(Y), edge(X, Y), color(X, C), color(Y, C).

% Факты о вершинах и рёбрах vertex(a). vertex(b). vertex(c). edge(a, b). edge(b, c). edge(c, a). ```

Решатель CLINGO найдёт два набора ответов: {color(a,1), color(b,2), color(c,1)} и {color(a,2), color(b,1), color(c,2)}.

¶Сравнение с другими парадигмами

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

¶Ограничения и критика

• Производительность: Для некоторых задач ASP-решатели могут быть медленнее специализированных алгоритмов (например, для задачи коммивояжёра).
• Сложность отладки: Поскольку ASP-программа не выполняется последовательно, отладка может быть затруднена.
• Ограниченная поддержка типов: В стандартном ASP нет встроенных типов данных (например, чисел с плавающей точкой), что требует дополнительных кодировок.
• Недостаток инструментов: По сравнению с языками общего назначения, экосистема ASP (IDE, библиотеки, отладчики) менее развита.

¶Перспективы развития

ASP активно развивается в направлении:

• Интеграции с машинным обучением: использование ASP для представления знаний в гибридных системах.
• Параллельных и распределённых решателей: для решения крупномасштабных задач.
• Расширения языка: добавление встроенных предикатов для работы с графами, временными рядами и неопределённостью.

¶Источники

• Gelfond, M., & Lifschitz, V. (1988). The stable model semantics for logic programming.
• Niemelä, I. (1999). Logic programs with stable model semantics as a constraint programming paradigm.
• Calimeri, F., et al. (2013). ASP-Core-2: Input language specification.
• Gebser, M., et al. (2012). Answer Set Solving in Practice.
• Brewka, G., Eiter, T., & Truszczyński, M. (2011). Answer set programming at a glance.