Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жасанды интеллект саласы
Branch of artificial intelligence
Автоматты жоспарлау және кестелеу, кейде жай ғана AI жоспарлау деп аталатын бұл сала, стратегияларды немесе әрекеттер тізбегін іске асырумен айналысатын жасанды интеллект тармағы болып табылады, әдетте бұл ақылды агенттер, автономды роботтар және ұшқышсыз көліктер арқылы орындалады. Классикалық басқару және жіктеу мәселелерінен өзгеше, шешімдер күрделі болып келеді және оларды көп өлшемді кеңістікте табу және оңтайландыру қажет. Жоспарлау шешім қабылдау теориясымен де байланысты. Белгілі ортада, қолжетімді модельдер болған жағдайда, жоспарлау офлайн режимінде жүзеге асырылуы мүмкін. Шешімдер орындау алдында табылып, бағалануы мүмкін. Динамикалық белгісіз ортада стратегияны көбінесе онлайн режимінде қайта қарау қажеттігі туады. Модельдер мен саясаттарға өзгерістер енгізілуі керек. Шешімдер көбінесе жасанды интеллектте жиі кездесетін, қайта-қайта сынақтар мен қателіктерге негізделген процестерге жүгінеді. Мұндай процестерге динамикалық бағдарламалау, күшейту арқылы оқыту және комбинаторлық оптимизация жатады. Жоспарлау мен кестелеуді сипаттау үшін қолданылатын тілдер көбінесе әрекеттер тілі деп аталады.
Automated planning and scheduling, sometimes denoted as simply AI planning, is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are complex and must be discovered and optimized in multidimensional space. Planning is also related to decision theory. In known environments with available models, planning can be done offline. Solutions can be found and evaluated prior to execution. In dynamically unknown environments, the strategy often needs to be revised online. Models and policies must be adapted. Solutions usually resort to iterative trial and error processes commonly seen in artificial intelligence. These include dynamic programming, reinforcement learning and combinatorial optimization. Languages used to describe planning and scheduling are often called action languages.
Доменге тәуелсіз жоспарлау
Жасанды интеллект жоспарлауда жоспарлаушылар әдетте домендік модельді (доменді модельдеуге мүмкіндік беретін әрекеттер жиынтығының сипаттамасы) және бастапқы күй мен мақсат арқылы анықталатын нақты мәселені енгізеді. Бұл, домендік модель берілмеген жағдайлардан өзгеше. Мұндай жоспарлаушылар "доменге тәуелсіз" деп аталады, олардың кең ауқымды домендердегі жоспарлау мәселелерін шеше алатынын көрсету үшін. Домендердің әдеттегі мысалдары: блоктарды үйіп қою, логистика, жұмыс процесін басқару және роботтардың тапсырмаларын жоспарлау. Сондықтан, бір доменге тәуелсіз жоспарлаушы осы әртүрлі домендердегі жоспарлау мәселелерін шешуге қолданылуы мүмкін. Ал маршрут жоспарлаушы – доменге тәуелді жоспарлаушының мысалы.
In AI planning, planners typically input a domain model (a description of a set of possible actions which model the domain) as well as the specific problem to be solved specified by the initial state and goal, in contrast to those in which there is no input domain specified. Such planners are called "domain independent" to emphasize the fact that they can solve planning problems from a wide range of domains. Typical examples of domains are block stacking, logistics, workflow management, and robot task planning. Hence a single domain independent planner can be used to solve planning problems in all these various domains. On the other hand, a route planner is typical of a domain specific planner.
Жоспарлау саласының модельдеу тілдері
Жоспарлау салаларын және нақты жоспарлау мәселелерін бейнелеуге ең көп қолданылатын тілдер, мысалы STRIPS және классикалық жоспарлау үшін PDDL, күй айнымалыларына негізделген. Әлемнің кез келген мүмкін күйі – күй айнымалыларына берілген мәндер жиынтығы, ал әрекеттер сол әрекет орындалғанда күй айнымалыларының мәндері қалай өзгеретінін анықтайды. Күй айнымалылары жиынтығы жиынтықтағы экспоненциалдық мөлшердегі күй кеңістігін тудыратындықтан, жоспарлау, көптеген басқа есептеу мәселелері сияқты, өлшемділік қарғысы мен комбинаторлық жарылысқа ұшырайды. Жоспарлау мәселелерін сипаттаудың балама тілі – иерархиялық міндеттер желісі, онда міндеттер жиынтығы беріледі және әрбір міндетті бастапқы әрекет арқылы іске асыруға болады немесе басқа міндеттер жиынтығына бөлуге болады. Бұл міндетті түрде күй айнымалыларын қамтымайды, бірақ шынайы қолдануларда күй айнымалылары міндеттер желісін сипаттауды жеңілдетеді.
The most commonly used languages for representing planning domains and specific planning problems, such as STRIPS and PDDL for Classical Planning, are based on state variables. Each possible state of the world is an assignment of values to the state variables, and actions determine how the values of the state variables change when that action is taken. Since a set of state variables induce a state space that has a size that is exponential in the set, planning, similarly to many other computational problems, suffers from the curse of dimensionality and the combinatorial explosion. An alternative language for describing planning problems is that of hierarchical task networks, in which a set of tasks is given, and each task can be either realized by a primitive action or decomposed into a set of other tasks. This does not necessarily involve state variables, although in more realistic applications state variables simplify the description of task networks.
Басқа проблемаларға қысқарту
ұсынысты қанағаттандыру мәселесіне (satplan) келтіру. модельді тексеруге келтіру. Екеуі де негізінен күй кеңістіктерін аралау мәселелері, ал классикалық жоспарлау мәселесі модельді тексеру мәселелерінің бір түріне жатады.
reduction to the propositional satisfiability problem (satplan). reduction to model checking both are essentially problems of traversing state spaces, and the classical planning problem corresponds to a subclass of model checking problems.
Уақытша жоспарлау
Уақытты жоспарлау классикалық жоспарлауға ұқсас әдістермен шешілуі мүмкін. Басты айырмашылық – бірнеше уақыт бойынша үстіртінде жатқан, сондай-ақ белгілі бір ұзақтығы бар әрекеттердің бір уақытта орындалу мүмкіндігінен туындайды, сондықтан күйдің анықтамасы қазіргі абсолютті уақыт туралы және әрбір іске қосылған әрекеттің орындалу барысы туралы ақпаратты қамтуы тиіс. Бұдан әрі, рационалды немесе нақты уақытпен жоспарлауда, күй кеңістігі классикалық жоспарлаудан немесе бүтін уақытпен жоспарлаудан өзгеше, шексіз болуы мүмкін. Уақытты жоспарлау белгісіздік туындағанда кестелеу мәселелерімен тығыз байланысты және оны уақытталған автоматтар арқылы түсінуге болады. Белгісіздігі бар қарапайым уақыт желісі (STNU) – басқарылатын әрекеттерді, белгісіз оқиғаларды және уақыт шектеулерін қамтитын кестелеу мәселесі. Мұндай мәселелер үшін динамикалық басқару – белгісіз оқиғалар байқалғанда басқарылатын әрекеттерді реактивті түрде іске қосуға арналған уақытты жоспарлау стратегиясын қажет ететін кестелеу түрі, осылайша барлық шектеулердің орындалуы кепілдендіріледі.
Temporal planning can be solved with methods similar to classical planning. The main difference is, because of the possibility of several, temporally overlapping actions with a duration being taken concurrently, that the definition of a state has to include information about the current absolute time and how far the execution of each active action has proceeded. Further, in planning with rational or real time, the state space may be infinite, unlike in classical planning or planning with integer time. Temporal planning is closely related to scheduling problems when uncertainty is involved and can also be understood in terms of timed automata. The Simple Temporal Network with Uncertainty (STNU) is a scheduling problem which involves controllable actions, uncertain events and temporal constraints. Dynamic Controllability for such problems is a type of scheduling which requires a temporal planning strategy to activate controllable actions reactively as uncertain events are observed so that all constraints are guaranteed to be satisfied.
Ықтималдық жоспарлау
Ықтималдық жоспарлау, егер күй кеңістігі жеткілікті кіші болса, мәнді итерация және саясатты итерация сияқты итеративтік әдістермен шешіледі. Ішінара байқау жағдайында, ықтималдық жоспарлау да итеративтік әдістермен шешіледі, бірақ күйлердің орнына сенімдер кеңістігі үшін анықталған құндылық функцияларының өрнегі қолданылады.
Probabilistic planning can be solved with iterative methods such as value iteration and policy iteration, when the state space is sufficiently small. With partial observability, probabilistic planning is similarly solved with iterative methods, but using a representation of the value functions defined for the space of beliefs instead of states.
Артықшылықтарға негізделген жоспарлау
Артықшылықтарға негізделген жоспарлауда мақсат – жоспар жасау ғана емес, сонымен қатар пайдаланушы көрсеткен артықшылықтарды қанағаттандыру. Сыйақыға негізделген жоспарлаудан, мысалы, MDP-лерге сәйкес келетінінен, айырмашылығы – артықшылықтар міндетті түрде нақты сандық мәнге ие болмауы мүмкін.
In preference based planning, the objective is not only to produce a plan but also to satisfy user specified preferences. A difference to the more common reward based planning, for example corresponding to MDPs, preferences don't necessarily have a precise numerical value.
Шартты жоспарлау
Детерминистік жоспарлау STRIPS жоспарлау жүйесімен енгізілді, ол иерархиялық жоспарлаушы болып табылады. Әрекеттердің атаулары тізбектей ретпен жазылады, және бұл робот үшін жоспар. Иерархиялық жоспарлауды автоматты түрде жасалған мінез-құлық ағашымен салыстыруға болады. Оның кемшілігі – әдеттегі мінез-құлық ағашы компьютерлік бағдарлама сияқты толыққанды емес. Яғни, мінез-құлық графының жазуында іс-әрекет командалары болады, бірақ циклдар немесе «if-then» операторлары жоқ. Шартты жоспарлау бұл шектеуді жеңіп, басқа бағдарламалау тілдерінен, мысалы, Паскальден белгілі бақылау ағынына ұқсас кеңейтілген жазу тәсілін ұсынады. Бұл бағдарламалық синтезге өте ұқсас, яғни жоспарлаушы интерпретатор орындай алатын бастапқы кодты құрайды. Шартты жоспарлаушының ерте мысалы – 1970 жылдардың ортасында ұсынылған «Warplan C». Құрделі жоспар, онда «if-then» операторлары бар, пен қарапайым тізбек арасындағы айырмашылық неде? Бұл жоспарды орындау кезіндегі белгісіздікпен байланысты. Яғни, жоспар жоспарлаушыға беймәлім сенсорлық сигналдарға реакция жасай алады. Жоспарлаушы алдын ала екі мүмкіндікті ұсынады. Мысалы, егер объект анықталса, А әрекеті орындалады, егер объект табылмаса, В әрекеті орындалады. Шартты жоспарлаудың маңызды артықшылығы – жартылай жоспарларды басқару қабілеті. Агенттің барлық нәрсені басынан соңына дейін жоспарлауға міндетті емес, ол мәселені бөліктерге бөле алады. Бұл күй кеңістігін азайтуға және күрделірек мәселелерді шешуге көмектеседі.
Deterministic planning was introduced with the STRIPS planning system, which is a hierarchical planner. Action names are ordered in a sequence and this is a plan for the robot. Hierarchical planning can be compared with an automatic generated behavior tree. The disadvantage is, that a normal behavior tree is not so expressive like a computer program. That means, the notation of a behavior graph contains action commands, but no loops or if then statements. Conditional planning overcomes the bottleneck and introduces an elaborated notation which is similar to a control flow, known from other programming languages like Pascal. It is very similar to program synthesis, which means a planner generates sourcecode which can be executed by an interpreter. An early example of a conditional planner is “Warplan C” which was introduced in the mid 1970s. What is the difference between a normal sequence and a complicated plan, which contains if then statements? It has to do with uncertainty at runtime of a plan. The idea is that a plan can react to sensor signals which are unknown for the planner. The planner generates two choices in advance. For example, if an object was detected, then action A is executed, if an object is missing, then action B is executed. A major advantage of conditional planning is the ability to handle partial plans. An agent is not forced to plan everything from start to finish but can divide the problem into chunks. This helps to reduce the state space and solves much more complex problems.
Төтенше жағдайларды жоспарлау
Біз қоршаған орта сенсорлар арқылы байқалатын, бірақ олардың қате болу мүмкіндігі бар болғанда "көзге көрінетін жоспарлау" туралы айтамыз. Осылайша, бұл жоспарлау агенті толық емес ақпарат негізінде әрекет ететін жағдай. Көзге көрінетін жоспарлау мәселесі үшін жоспар енді іс-қимылдар тізбегі емес, шешім ағашы болып табылады, себебі жоспардың әр қадамы классикалық жоспарлаудағыдай бір ғана толық байқалатын күйдің орнына күйлер жиынтығымен бейнеленеді. Таңдалған іс-қимылдар жүйенің күйіне байланысты. Мысалы, жаңбыр жауса, агент қолшатыр алып кетеді, ал жаңбыр жаумаса, оны алып кетпеуі мүмкін. Майкл Л. Литтман 1998 жылы көрсеткендей, тармақталған іс-қимылдармен жоспарлау мәселесі EXPTIME толық болатын. Көзге көрінетін жоспарлаудың нақты бір жағдайы "толық байқалатын және детерминистік емес" (FOND) мәселелерімен көрсетіледі. Егер мақсат LTLf (шекті іздемедегі сызықтық уақыт логикасы) арқылы көрсетілсе, мәселе әрқашан EXPTIME толық болады, ал мақсат LDLf арқылы көрсетілсе, 2EXPTIME толық болады.
We speak of "contingent planning" when the environment is observable through sensors, which can be faulty. It is thus a situation where the planning agent acts under incomplete information. For a contingent planning problem, a plan is no longer a sequence of actions but a decision tree because each step of the plan is represented by a set of states rather than a single perfectly observable state, as in the case of classical planning. The selected actions depend on the state of the system. For example, if it rains, the agent chooses to take the umbrella, and if it doesn't, they may choose not to take it. Michael L. Littman showed in 1998 that with branching actions, the planning problem becomes EXPTIME complete. A particular case of contiguous planning is represented by FOND problems for "fully observable and non deterministic". If the goal is specified in LTLf (linear time logic on finite trace) then the problem is always EXPTIME complete and 2EXPTIME complete if the goal is specified with LDLf.
Қалыпты жоспарлау
Қалыпты жоспарлау – агент жүйенің жағдайы туралы нақты білмейтін және ешқандай байқау мүмкіндігіне ие болмайтын жағдай. Агент нақты әлем туралы болжамдар жасаса да, оларды сезімталдық әрекеттері арқылы тексеріп алуға мүмкіндік болмайды. Мұндай мәселелер классикалық жоспарлау әдістеріне ұқсас тәсілдермен шешіледі, бірақ қазіргі жағдай туралы белгісіздік болғандықтан, күй кеңістігі проблеманың мөлшеріне қарай экспоненциалды түрде өседі. Қалыпты жоспарлау мәселесінің шешімі – әрекеттер тізбегі. Хаслум мен Йонссон қалыпты жоспарлау мәселесі EXPSPACE-ке толық және бастапқы жағдай белгісіз болғанда және әрекеттердің нәтижелері анықталмағанда 2EXPTIME-ға толық екенін көрсетті.
Conformant planning is when the agent is uncertain about the state of the system, and it cannot make any observations. The agent then has beliefs about the real world, but cannot verify them with sensing actions, for instance. These problems are solved by techniques similar to those of classical planning, but where the state space is exponential in the size of the problem, because of the uncertainty about the current state. A solution for a conformant planning problem is a sequence of actions. Haslum and Jonsson have demonstrated that the problem of conformant planning is EXPSPACE complete, and 2EXPTIME complete when the initial situation is uncertain, and there is non determinism in the actions outcomes.
Жоспарлау жүйелерін енгізу
Хаббл ғарыш телескопы SPSS деп аталатын қысқа мерзімдік жүйе және Spike деп аталатын ұзақ мерзімді жоспарлау жүйесін пайдаланады.
The Hubble Space Telescope uses a short term system called SPSS and a long term planning system called Spike .