Czym jest Programowanie zbioru odpowiedzi (answer set programming, ASP)?
Programowanie zbioru odpowiedzi stanowi deklaratywne podejście do modelowania problemów dyskretnych, w którym zamiast opisywać kolejność obliczeń, projektant podaje warunki, jakie musi spełniać rozwiązanie. Efektem działania systemu ASP jest zestaw zbiorów literali zwanych zbiorami odpowiedzi, odpowiadających spójnym „światom” logicznym spełniającym zadane reguły. Formalne podstawy ASP wywodzą się z semantyki stabilnych modeli logiki programowania z negacją (Gelfond, Lifschitz 1988), a samo pojęcie ASP zostało upowszechnione w połowie lat dziewięćdziesiątych na Uniwersytecie Teksasu w Austin oraz na Uniwersytecie Helsińskim.
Jak dokładnie działa Programowanie zbioru odpowiedzi (answer set programming, ASP)
Program ASP składa się z reguł postaci głowa ← ciało, gdzie ciało może zawierać zarówno pozytywne, jak i negatywne literały. Najpierw następuje uziemienie programu, czyli rozwinięcie reguł o wszystkie możliwe podstawienia stałych. Następnie solver, np. clingo lub dlv, wyszukuje zbiory stabilne, korzystając z heurystyk podobnych do stosowanych w rozwiązywaniu problemu spełnialności. Wynik zwracany jest jako wybrane zbiory atomów prawdziwych, które spełniają wszystkie ograniczenia programu oraz kryterium minimalności.
Kontekst historyczny
Za pionierów podejścia uważa się Vladimira Lifschitza, Michaela Gelfonda oraz Ilkkę Niemelä, którzy w latach 1991–1999 opracowali pierwsze definicje semantyczne i wczesne systemy, takie jak smodels. W kolejnej dekadzie środowiska Uniwersytetu w Poczdamie (zespół Potassco) oraz Uniwersytetu w Trydencie (Nicola Leone) przygotowały wydajne solvery clingo i dlv, torując drogę do zastosowań przemysłowych.
Zastosowania w praktyce
ASP wykorzystywane jest w harmonogramowaniu zadań produkcyjnych, konfiguracji złożonych produktów, planowaniu ruchu robotów czy analizie sieci biologicznych. Przykładowo, automatyczny planista dla floty dronów może zostać opisany kilkudziesięcioma regułami dotyczącymi ograniczeń czasowych, pojemności akumulatorów i stref zakazu lotów; solver ASP w ułamku sekundy zwróci wszystkie dopuszczalne grafiki misji. W porównaniu z klasycznymi algorytmami wyszukiwania stanów, podejście deklaratywne pozwala skrócić czas projektowania, gdyż inżynier definiuje „co” ma być spełnione, a nie „jak” do tego dojść.
Zalety i ograniczenia
Główną zaletą jest zwartość zapisu i czytelność, dzięki czemu modyfikacja modelu wymaga zwykle zmiany pojedynczych reguł. ASP ułatwia też obsługę negacji i nieskończonej domeny dzięki wbudowanej semantyce negacji z brakiem dowodu. Ograniczeniem bywa natomiast proces uziemiania, który w bardzo dużych domenach może prowadzić do eksplozji liczby reguł i zapotrzebowania na pamięć.
Na co uważać?
Podczas projektowania systemu ASP warto zwrócić uwagę na wielkość domen, unikać zbędnej generacji obiektów oraz stosować zaawansowane techniki modularyzacji lub uziemiania częściowego. Kluczową kwestią pozostaje dobór solvera i jego parametrów, ponieważ różne heurystyki mogą znacząco wpłynąć na czas znajdowania zbiorów odpowiedzi.
Dodatkowe źródła
Rozszerzone omówienie formalnych podstaw dostępne jest w artykule The Answer Set Programming Paradigm. Wprowadzenie o charakterze encyklopedycznym można znaleźć w haśle Wikipedia: Programowanie zbioru odpowiedzi. Aktualne wersje solverów i przykłady kodu publikowane są na stronie Potassco – Tools for ASP.
