Zautomatyzowane planowanie i harmonogramowanie - Automated planning and scheduling

Część serii na
Sztuczna inteligencja
Główne cele
Podejścia
Filozofia
Historia
Technologia
Słownik

Zautomatyzowane planowanie i harmonogramowanie , czasami określane jako po prostu planowanie AI , to gałąź sztucznej inteligencji, która dotyczy realizacji strategii lub sekwencji działań, zwykle wykonywanych przez inteligentnych agentów , autonomiczne roboty i bezzałogowe pojazdy . W przeciwieństwie do klasycznych problemów z kontrolą i klasyfikacją , rozwiązania są złożone i muszą zostać odkryte i zoptymalizowane w wielowymiarowej przestrzeni. Planowanie jest również związane z teorią decyzji .

W znanych środowiskach z dostępnymi modelami planowanie można przeprowadzić offline. Rozwiązania można znaleźć i ocenić przed wykonaniem. W dynamicznie nieznanych środowiskach strategia często wymaga weryfikacji online. Należy dostosować modele i polityki. Rozwiązania zazwyczaj wykorzystują iteracyjne procesy prób i błędów powszechnie spotykane w sztucznej inteligencji . Obejmują one programowanie dynamiczne , uczenie się przez wzmacnianie i optymalizację kombinatoryczną . Języki używane do opisu planowania i harmonogramowania są często nazywane językami działania .

Przegląd

Dalsze informacje: Przeszukiwanie przestrzeni stanów

Biorąc pod uwagę opis możliwych stanów początkowych świata, opis pożądanych celów i opis zestawu możliwych działań, problem planowania polega na zsyntetyzowaniu planu, który jest gwarantowany (w zastosowaniu do któregokolwiek ze stanów początkowych) generowanie stanu, który zawiera pożądane cele (taki stan nazywa się stanem celu).

Trudność planowania zależy od przyjętych założeń upraszczających. W zależności od właściwości, jakie problemy mają w kilku wymiarach, można zidentyfikować kilka klas problemów planistycznych.

  • Czy działania są deterministyczne czy niedeterministyczne? Czy dla działań niedeterministycznych są dostępne związane z nimi prawdopodobieństwa?
  • Czy zmienne stanu są dyskretne czy ciągłe? Jeśli są dyskretne, czy mają tylko skończoną liczbę możliwych wartości?
  • Czy stan obecny można zaobserwować jednoznacznie? Może być pełna obserwowalność i częściowa obserwowalność.
  • Ile jest stanów początkowych, skończonych lub arbitralnie wielu?
  • Czy działania mają określony czas trwania?
  • Czy można wykonać kilka działań jednocześnie, czy tylko jedno działanie w danym momencie jest możliwe?
  • Czy celem planu jest osiągnięcie wyznaczonego stanu celu, czy maksymalizacja funkcji nagrody ?
  • Czy jest tylko jeden agent, czy jest kilku agentów? Czy agenci współpracują czy są samolubni? Czy wszyscy agenci budują własne plany oddzielnie, czy też plany są konstruowane centralnie dla wszystkich agentów?

Najprostszy możliwy problem planowania, znany jako klasyczny problem planowania, jest określony przez:

  • unikalny znany stan początkowy,
  • działania nietrwałe,
  • działania deterministyczne,
  • które można zabrać tylko raz na raz,
  • i jednego agenta.

Ponieważ stan początkowy jest znany jednoznacznie, a wszystkie działania są deterministyczne, stan świata po dowolnej sekwencji działań można dokładnie przewidzieć, a kwestia obserwowalności nie ma znaczenia dla klasycznego planowania.

Co więcej, plany można zdefiniować jako sekwencje działań, ponieważ zawsze wiadomo z góry, które działania będą potrzebne.

W przypadku niedeterministycznych działań lub innych zdarzeń poza kontrolą agenta możliwe wykonania tworzą drzewo, a plany muszą określać odpowiednie działania dla każdego węzła drzewa.

Procesy decyzyjne Markowa w czasie dyskretnym (MDP) to problemy z planowaniem związane z:

  • działania nietrwałe,
  • działania niedeterministyczne z prawdopodobieństwami,
  • pełna obserwowalność,
  • maksymalizacja funkcji nagrody,
  • i jednego agenta.

Kiedy pełną obserwowalność zastępuje się częściową obserwowalnością, planowanie odpowiada częściowo obserwowalnemu procesowi decyzyjnemu Markowa (POMDP).

Jeśli jest więcej niż jeden agent, mamy planowanie wieloagentowe , które jest ściśle związane z teorią gier .

Planowanie niezależne od domeny

W planowaniu AI planiści zazwyczaj wprowadzają model domeny (opis zestawu możliwych działań modelujących dziedzinę) oraz konkretny problem do rozwiązania określony przez stan początkowy i cel, w przeciwieństwie do tych, w których nie ma określona domena wejściowa. Tacy planiści są nazywani „niezależnymi od domeny”, aby podkreślić fakt, że mogą rozwiązywać problemy planowania z wielu dziedzin. Typowymi przykładami domen są układanie bloków, logistyka, zarządzanie przepływem pracy i planowanie zadań robotów. W związku z tym do rozwiązywania problemów związanych z planowaniem we wszystkich tych różnych dziedzinach można użyć jednego niezależnego planera. Z drugiej strony, planowanie trasy jest typowe dla planowania branżowego.

Planowanie języków modelowania domeny


Języki najczęściej używane do reprezentowania dziedzin planowania i określonych problemów planowania, takie jak STRIPS i PDDL do planowania klasycznego, są oparte na zmiennych stanu. Każdy możliwy stan świata jest przypisaniem wartości do zmiennych stanu, a akcje określają, jak wartości zmiennych stanu zmieniają się po wykonaniu tej akcji. Ponieważ zbiór zmiennych stanu indukuje przestrzeń stanów, która ma rozmiar wykładniczy w zbiorze, planowanie, podobnie jak wiele innych problemów obliczeniowych, cierpi z powodu przekleństwa wymiarowości i eksplozji kombinatorycznej .

Alternatywnym językiem opisującym problemy planowania są hierarchiczne sieci zadań , w których dany jest zestaw zadań, a każde zadanie można zrealizować za pomocą prymitywnej czynności lub rozłożyć na zestaw innych zadań. Niekoniecznie wiąże się to ze zmiennymi stanu, chociaż w bardziej realistycznych aplikacjach zmienne stanu upraszczają opis sieci zadaniowych.

Algorytmy planowania

Planowanie klasyczne

Zobacz także: anomalia Sussmana

Redukcja do innych problemów

  • redukcja do problemu spełnialności zdań ( satplan ).
  • redukcja do sprawdzania modelu - oba są zasadniczo problemami przechodzenia przez przestrzenie stanów, a klasyczny problem planowania odpowiada podklasie problemów sprawdzania modelu.

Planowanie czasowe

Planowanie czasowe można rozwiązać metodami podobnymi do planowania klasycznego. Główna różnica polega na tym, że ze względu na możliwość kilku nakładających się czasowo działań z czasem trwania podejmowanych jednocześnie, definicja stanu musi zawierać informacje o bieżącym czasie bezwzględnym oraz o tym, jak daleko zaszło wykonanie każdej aktywnej akcji. Ponadto, w planowaniu w czasie racjonalnym lub rzeczywistym, przestrzeń stanów może być nieskończona, w przeciwieństwie do klasycznego planowania lub planowania z czasem całkowitym. Planowanie czasowe jest ściśle związane z problemami planowania . Planowanie czasowe może być również rozumiane w kategoriach automatów czasowych .

Planowanie probabilistyczne

Główne artykuły: Proces decyzyjny Markowa i częściowo obserwowalny proces decyzyjny Markowa

Planowanie probabilistyczne można rozwiązać za pomocą metod iteracyjnych, takich jak iteracja wartości i iteracja polityki , gdy przestrzeń stanów jest wystarczająco mała. W przypadku częściowej obserwowalności planowanie probabilistyczne rozwiązuje się w podobny sposób metodami iteracyjnymi, ale za pomocą reprezentacji funkcji wartości zdefiniowanych dla przestrzeni przekonań zamiast stanów.

Planowanie oparte na preferencjach

Główny artykuł: Planowanie w oparciu o preferencje

W planowaniu opartym na preferencjach celem jest nie tylko stworzenie planu, ale także spełnienie preferencji określonych przez użytkownika . W odróżnieniu od bardziej powszechnego planowania opartego na nagrodach, na przykład odpowiadającego MDP, preferencje niekoniecznie mają dokładną wartość liczbową.

Planowanie warunkowe

Planowanie deterministyczne zostało wprowadzone w systemie planowania STRIPS , który jest planistą hierarchicznym. Nazwy akcji są uporządkowane w kolejności i jest to plan dla robota. Planowanie hierarchiczne można porównać z automatycznie generowanym drzewem zachowań . Wadą jest to, że normalne drzewo zachowań nie jest tak wyraziste, jak program komputerowy. Oznacza to, że zapis grafu zachowania zawiera polecenia akcji, ale nie zawiera pętli ani instrukcji if-then. Planowanie warunkowe pokonuje wąskie gardło i wprowadza skomplikowaną notację, która jest podobna do przepływu sterowania , znanego z innych języków programowania, takich jak Pascal . Jest to bardzo podobne do syntezy programu , co oznacza, że ​​planista generuje kod źródłowy, który może zostać wykonany przez interpretera.

Wczesnym przykładem warunkowego planera jest „Warplan-C”, który został wprowadzony w połowie lat 70-tych. Jaka jest różnica między normalną sekwencją a skomplikowanym planem, który zawiera instrukcje „jeśli-to”? Ma to związek z niepewnością w czasie wykonywania planu. Pomysł polega na tym, że plan może reagować na sygnały z czujników, które są nieznane planiście. Planista z góry generuje dwie opcje. Na przykład, jeśli obiekt został wykryty, to wykonywana jest akcja A, jeśli brakuje obiektu, to wykonywana jest akcja B. Główną zaletą planowania warunkowego jest możliwość obsługi planów częściowych . Środek nie jest zmuszony planować wszystko od początku do końca, ale można podzielić problem na kawałki . Pomaga to zmniejszyć przestrzeń stanów i rozwiązuje znacznie bardziej złożone problemy.

Planowanie warunkowe

Mówimy o „planowaniu awaryjnym”, gdy środowisko można obserwować za pomocą czujników, które mogą być wadliwe. Jest to więc sytuacja, w której osoba planująca działa na podstawie niepełnych informacji. W przypadku problemu planowania warunkowego plan nie jest już sekwencją działań, ale drzewem decyzyjnym, ponieważ każdy krok planu jest reprezentowany przez zbiór stanów, a nie pojedynczy, doskonale obserwowalny stan, jak w przypadku planowania klasycznego. Wybrane akcje zależą od stanu systemu. Na przykład, jeśli pada deszcz, agent decyduje się wziąć parasol, a jeśli nie, mogą go nie brać.

Michael L. Littman wykazał w 1998 roku, że dzięki rozgałęziającym się działaniom, problem planowania staje się EXPTIME -kompletny . Szczególny przypadek planowania ciągłego reprezentowany jest przez problemy FOND - dla „w pełni obserwowalnych i niedeterministycznych”. Jeśli cel jest określony w LTLf (logika czasu liniowego na skończonym śledzeniu), to problem jest zawsze zakończony EXPTIME i 2 EXPTIME-complete, jeśli cel jest określony za pomocą LDLf.

Zgodne planowanie

Planowanie zgodne ma miejsce, gdy agent nie jest pewien stanu systemu i nie może dokonywać żadnych obserwacji. Agent ma wtedy przekonania na temat prawdziwego świata, ale nie może ich zweryfikować na przykład za pomocą działań wyczuwających. Te problemy są rozwiązywane za pomocą technik podobnych do tych stosowanych w klasycznym planowaniu, ale gdzie przestrzeń stanów ma wykładniczy rozmiar problemu, z powodu niepewności co do aktualnego stanu. Rozwiązaniem problemu planowania zgodnego jest sekwencja działań. Haslum i Jonsson wykazali, że problem planowania zgodnego jest zakończony EXPSPACE i 2 EXPTIME-zakończony, gdy sytuacja początkowa jest niepewna, a wyniki działań są niedeterministyczne.

Wdrażanie systemów planowania

Zobacz też

Listy

Bibliografia

Dalsza lektura

Linki zewnętrzne