Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
СТАНФОРД зерттеу институтының проблема шешушісі, STRIPS аббревиатурасымен белгілі, 1971 жылы SRI International-да Ричард Фикс және Нильс Нильссон жасаған автоматтандырылған жоспарлау құралы. Кейін осы атау осы жоспарлау құралына берілетін кіріс мәліметтерінің ресми тілін атау үшін де қолданылды. Бұл тіл бүгінгі күні қолданылатын автоматтандырылған жоспарлау мәселелерін сипаттауға арналған көптеген тілдердің негізі болып табылады; мұндай тілдер көбінесе іс-әрекет тілдері деп аталады. Бұл мақалада тек тіл туралы, жоспарлау құралы туралы емес, айтылады.
The Stanford Research Institute Problem Solver, known by its acronym STRIPS, is an automated planner developed by Richard Fikes and Nils Nilsson in 1971 at SRI International. The same name was later used to refer to the formal language of the inputs to this planner. This language is the base for most of the languages for expressing automated planning problem instances in use today; such languages are commonly known as action languages. This article only describes the language, not the planner.
Ұзартулар
Жоғарыда көрсетілген тіл – бұл STRIPS-тің логикалық нұсқасы; практикада шарттар көбінесе объектілерге қатысты болады: мысалы, роботтың орны предикат арқылы модельделуі мүмкін, ал – роботтың Room1 бөлмесінде екенін көрсетеді. Мұндай жағдайда, әрекеттерде еркін айнымалылар болуы мүмкін, олар ашық түрде сандықпен беріледі. Басқаша айтқанда, әрекет – әрбір еркін айнымалыны нақты мәнмен алмастыру арқылы алынатын барлық мүмкін логикалық әрекеттерді білдіреді. Бастапқы күй жоғарыда сипатталған тілде толыққанды белгілі деп есептеледі: -де көрсетілмеген шарттардың бәрі жалған деп қарастырылады. Бұл көбінесе шектеулі болжам, себебі бастапқы жағдай толық белгілі емес жоспарлау есептерінің көптеген мысалдары бар. STRIPS-тің кеңейтілген нұсқалары ішінара белгілі бастапқы жағдайларды шешу үшін жасалған.
The above language is actually the propositional version of STRIPS; in practice, conditions are often about objects: for example, that the position of a robot can be modeled by a predicate , and means that the robot is in Room1. In this case, actions can have free variables, which are implicitly existentially quantified. In other words, an action represents all possible propositional actions that can be obtained by replacing each free variable with a value. The initial state is considered fully known in the language described above: conditions that are not in are all assumed false. This is often a limiting assumption, as there are natural examples of planning problems in which the initial state is not fully known. Extensions of STRIPS have been developed to deal with partially known initial states.
Күрделілігі
Пропозициялық STRIPS инстанциясы үшін қандай да бір жоспар бар-жоқ екенін анықтау PSPACE толық проблемасы болып табылады. Полиномиалдық уақытта жоспардың бар екенін анықтау немесе кемінде оны NP толық проблемаға дейін айналдыру үшін әртүрлі шектеулер қойылуы мүмкін.
Deciding whether any plan exists for a propositional STRIPS instance is PSPACE complete. Various restrictions can be enforced in order to decide if a plan exists in polynomial time or at least make it an NP complete problem.
Макро-оператор
Маймыл мен банан мәселесінде робот маймыл төбедегі бананға жету үшін бірқатар әрекеттерді орындауы тиіс. Бір ғана әрекет ойынның жағдайын сәл өзгертеді. Жоспарлау процесін жеңілдету үшін, қалыпты ережелерде жоқ абстрактілі әрекетті ойлап табу мағыналы. Супер-әрекет төменгі деңгейдегі әрекеттерден құралады және жоғары деңгейдегі мақсаттарға жете алады. Бұл артықшылықтың нәтижесінде есептеу күрделілігі төмендейді және шешушіге ұзақ тапсырмаларды жоспарлау мүмкіндігі туады. Бір домен үшін жаңа макрооператорларды генетикалық бағдарламалау арқылы табуға болады. Мақсаты – доменді жоспарлау емес, ал алдын ала кезеңде доменді әлдеқайда жылдам шешуге мүмкіндік беретін эвристика құру. Күшейтілген оқыту контекстінде макрооператорлар опция деп аталады. AI жоспарлаудағы анықтамасына сәйкес, идеясы – уақытша абстракция (ұзақ мерзімділік) ұсыну және ойын күйін жоғары деңгейде тікелей өзгерту.
In the monkey and banana problem, the robot monkey has to execute a sequence of actions to reach the banana at the ceiling. A single action provides a small change in the game. To simplify the planning process, it make sense to invent an abstract action, which isn't available in the normal rule description. The super action consists of low level actions and can reach high level goals. The advantage is that the computational complexity is lower, and longer tasks can be planned by the solver. Identifying new macro operators for a domain can be realized with genetic programming. The idea is, not to plan the domain itself, but in the pre step, a heuristics is created that allows the domain to be solved much faster. In the context of reinforcement learning, a macro operator is called an option. Similar to the definition within AI planning, the idea is, to provide a temporal abstraction (span over a longer period) and to modify the game state directly on a higher layer.