Czym jest System przejść (transition system)?
System przejść to formalny model opisujący, jak stan pewnego procesu może zmieniać się pod wpływem dozwolonych operacji. W najprostszym ujęciu składa się z trzech elementów: zbioru stanów, zbioru akcji i relacji przejścia określającej, które stany mogą następować po sobie. Koncepcja wywodzi się z badań nad automatami i wczesnymi metodami weryfikacji programów, prowadzonych m.in. w latach sześćdziesiątych w Carnegie Mellon University przez Allena Newella i Herberta Simona, a jej współczesne rozwinięcia znajdują zastosowanie w planowaniu, analizie języka naturalnego czy weryfikacji systemów krytycznych.
Jak dokładnie działa System przejść?
Model rozpoczyna się od stanu początkowego, który pod wpływem dopuszczalnych akcji może ewoluować w kolejne stany, tworząc ścieżkę obliczeń. Algorytmy sztucznej inteligencji, takie jak wyszukiwanie w przestrzeni stanów czy planowanie STRIPS, eksplorują tę sieć możliwych przejść, aby odnaleźć sekwencję akcji prowadzącą do stanu docelowego. Dzięki temu abstrakcyjnemu ujęciu można porównywać, analizować lub weryfikować nawet bardzo różnorodne procesy: od ruchu robota w magazynie po składnię zdania w parserze zależnościowym.
Schemat formalny
System przejść definiuje się jako trójkę (S, A, →), gdzie S oznacza skończony lub nieskończony zbiór stanów, A zestaw akcji, a → relację ⊆ S × A × S. Każdy trójkowy rekord
Zastosowania w praktyce
W planowaniu klasycznym system przejść reprezentuje całą przestrzeń możliwych konfiguracji świata, którą algorytmy wyszukiwania, takie jak A* czy heurystyka h*, przeszukują w poszukiwaniu planu. W lingwistyce komputerowej parsery typu shift-reduce traktują częściowo przetworzone zdanie jako stan, a operacje przesunięcia lub redukcji jako akcje, co pozwala w elegancki sposób modelować składnię naturalną. W weryfikacji modelowej, szczególnie w narzędziach takich jak SPIN czy NuSMV, system przejść opisuje zachowanie programu, a sprawdzanie własności odbywa się poprzez przeglądanie wszystkich możliwych ścieżek.
Zalety i ograniczenia
Niewątpliwą zaletą systemu przejść jest jego uniwersalność: ten sam formalizm potrafi opisać zarówno prosty automat skończony, jak i złożone środowisko wieloagentowe. Modelowanie w postaci stanów i akcji ułatwia ponadto stosowanie sprawdzonych technik wyszukiwania, heurystyk oraz logik temporalnych. Wadą może być natomiast eksplozja przestrzeni stanów, szczególnie gdy liczba możliwych konfiguracji rośnie wykładniczo, co utrudnia skalowanie w dużych aplikacjach. Konieczne staje się wówczas stosowanie abstrakcji, kompresji stanów lub uczenia się heurystyk.
Na co uważać?
Projektując system przejść dla realnego zadania warto zwrócić uwagę na dwie kwestie. Po pierwsze, granica pomiędzy dokładnością modelu a jego złożonością jest krucha; zbyt szczegółowy opis doprowadzi do problemów obliczeniowych, zbyt uproszczony straci wartość predykcyjną. Po drugie, deterministyczność akcji nie zawsze jest naturalna w środowiskach probabilistycznych. W takich przypadkach lepiej rozważyć rozszerzenia w postaci procesów decyzyjnych Markowa lub uwzględnić prawdopodobieństwa bezpośrednio w relacji przejścia.
Dodatkowe źródła
Osoby chcące pogłębić wiedzę znajdą solidne fundamenty w rozdziałach o planowaniu podręcznika Artificial Intelligence: A Modern Approach. Dla lingwistycznych przykładów polecam pracę Joakima Nivre’a „An Efficient Algorithm for Shift-Reduce Parsing”. Zagadnienia weryfikacji modelowej zostały natomiast wyczerpująco omówione w artykule Holzmann’a „The SPIN Model Checker”. Warto również zajrzeć do hasła System przejść w Wikipedii oraz do przeglądowego artykułu na arXiv „Symbolic Search in AI Planning”.
