Świat bloków
Świat bloków jest domeną planowania w sztucznej inteligencji . Algorytm jest podobny do zestawu drewnianych klocków o różnych kształtach i kolorach leżących na stole. Celem jest zbudowanie jednego lub więcej pionowych stosów bloków. W danym momencie można przesuwać tylko jeden klocek: można go położyć na stole lub na innym klocku. Z tego powodu żadne bloki, które w danym momencie znajdują się pod innym blokiem, nie mogą zostać przesunięte. Co więcej, niektóre rodzaje bloków nie mogą mieć na sobie innych bloków.
Prostota tego świata zabawek łatwo nadaje się do klasycznych symbolicznych podejść do sztucznej inteligencji, w których świat jest modelowany jako zestaw abstrakcyjnych symboli, co do których można uzasadnić.
Motywacja
Sztuczną inteligencję można badać w teorii i praktycznych zastosowaniach. Problem z większością praktycznych zastosowań polega na tym, że inżynierowie nie wiedzą, jak zaprogramować system AI. Zamiast w ogóle odrzucać wyzwanie, pomysł polega na wynalezieniu łatwej do rozwiązania dziedziny, którą nazywa się problemem zabawkowym . Problemy z zabawkami zostały wymyślone w celu zaprogramowania sztucznej inteligencji, która może je rozwiązać. Domena świata bloków jest przykładem problemu z zabawką. Jego główną przewagą nad bardziej realistycznymi aplikacjami AI jest to, że dostępnych jest wiele algorytmów i programów, które mogą poradzić sobie z sytuacją. Pozwala to porównywać ze sobą różne teorie.
W swojej podstawowej formie problem świata bloków składa się z kostek tego samego rozmiaru, które mają kolor czarny. Mechaniczne ramię robota musi podnosić i układać kostki. Bardziej skomplikowane pochodne problemu składają się z kostek o różnych rozmiarach, kształtach i kolorach. Z perspektywy algorytmu świat bloków jest np-trudnym problemem wyszukiwania i planowania. Zadanie polega na doprowadzeniu systemu ze stanu początkowego do stanu docelowego.
automatycznego planowania i harmonogramowania jest zwykle opisywany w notacji Planning Domain Definition Language ( PDDL ), który jest językiem planowania sztucznej inteligencji do zadań manipulacji symbolami. Jeśli coś zostało sformułowane w notacji PDDL, nazywa się to domeną. Dlatego zadanie zszywania bloków jest domeną światową bloków, która pozostaje w przeciwieństwie do innych problemów planowania, takich jak domena robotów portowych oraz problem małpy i banana.
Przykładowa konfiguracja w świecie bloków
Tezy/projekty, które odbyły się w świecie bloków
- SHRDLU Terry'ego Winograda
- Nauka opisów strukturalnych Patricka Winstona na podstawie przykładów i kopii demonstracyjnej
- Anomalia Sussmana Geralda Jaya Sussmana
Problem decyzyjny (Gupta i Nau, 1992): Biorąc pod uwagę początkowy świat bloków, końcowy świat bloków i liczbę całkowitą L > 0, czy istnieje sposób na przesunięcie bloków w celu zmiany pozycji początkowej na pozycję końcową za pomocą L lub mniej kroków ?
Ten problem decyzyjny jest NP-trudny .
Zobacz też
Źródła
- Russell, Stuart J .; Norvig, Peter (2003), Sztuczna inteligencja: nowoczesne podejście (wyd. 2), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2