Ավտոմատացված պլանավորում

Ավտոմատացված պլանավորում, երբեմն նշվում է որպես ԱԻ պլանավորմում^[1], արհեստական բանականության հիմնական նպատակներից է, այն վերաբերում է ալգորիթմների կամ գործողությունների իրականացմանը, որոնք կատարվում են խելացի ագենտների, ավտոմատ ռոբոտների և անօդաչու փոխադրամիջոցների կողմից։ Ի տարբերություն դասական կառավարման և դասակարգման խնդիրների, այստեղ լուծումները բարդ են, և դրանք պետք է հայտնաբերվեն ու օպտիմիզացվեն բազմաչափ տարածությունում։ Պլանավորումը կապված է նաև որոշումների տեսության հետ։

Մեզ հայտնի միջավայրում համապատասխան սարքերով պլանավորումը կարող է կատարվել առանց համացանցի, լուծումները կարող են գտնվել և գնահատվել նախքան կատարումը։ Անհայտ միջավայրում լուծման ալգորիթմները հաճախ պետք է վերանայվեն առցանց, մոդելներն ու կանոնները պետք է համաձայնեցվեն, իսկ լուծումները սովորաբար օգտվում են փորձառությունից և սխալ գործընթացներից, որոնք էլ դիտվում են որպես արհեստական ինտելեկտ։ Սրանք ներառում են դինամիկ ծրագրավորում, ուսուցման ամրապնդում և կոմբինատորիկական օպտիմալացում։ Այն լեզուները, որոնք նկարագրում են պլանավորումը հաճախ կոչվում են գործողության լեզուներ։

Համառոտ նկարագրություն

Հաշվի առնելով իրերի դրությունը, ցանկալի նպատակները, ինչպես նաև հնարավոր գործողությունների մի շարք նկարագրությունը, պլանավորման խնդիրն է գտնել նախագիծ, որը երաշխավորում է ստեղծել վիճակ, որը պարունակում է ցանկալի նպատակները (այդպիսի վիճակը կոչվում է նպատակային վիճակ)։

Պլանավորման դժվարությոնը կախված է կիրառվող ենթադրությունների պարզեցումից։ Պլանավորման որոշ կարգեր կարող են նախագծվել կախված այն հատկություններից, որոնք ունեն խնդիրները տարբեր հարթություններում։

Արդյո՞ք գործողությունները վճռորոշ են, թե ոչ։ Ոչ վճռորոշ գործողությունների համար արդյո՞ք կան կապված հավանականություններ։
Վիճակի փոփոխականները դիսկրե՞տ են թե՞ շարունակական։ Եթե դրանք դիկրետ են, արդյո՞ք դրանք ունեն միայն սահմանափակ քանակությամբ հնարավոր արժեքներ։
Կարո՞ղ է ներկայի վիճակը դիտարկվել միարժեքորեն։ Կարող է լինել լիարժեք կամ մասնակի դիտողականություն։
Քանի՞ սկզբնական վիճակ կա, վերջավոր կամ կամայականորեն շատ։
Գործողություններն ունե՞ն տևողություն։
Կարո՞ղ են մի քանի գործողություններ ձեռնարկվել միաժամանակ, թե՞ միայն մեկ գործողություն է հնարավոր։
Արդյո՞ք ծրագրի նպատակն է հասնել նախատեսված վիճակին, թե՞ առավելագույնի հասցնել պարգևատրման ֆունկցիան։
Միայն մեկ գործակալ, թե մի քանի գործակալներ կան։ Գործակալները համագործակցո՞ւմ են, թե՞ եսասեր են։ Արդյո՞ք բոլոր գործակալները կառուցում են իրենց ծրագրերը առանձին-առանձին, թե՞ պլանները կենտրոնացած են բոլոր գործակալների համար։

Պլանավորման ամենապարզ հնարավոր խնդիրը, որը հայտնի է որպես դասական պլանավորման խնդիր^[2], որոշվում է հետևյալով.

հայտնի եզակի նախնական վիճակ,
անժամկետ գործողություններ,
վճռորոշ գործողություններ,
որը տվյալ ժամանակում կարող է կատարվել միայն մեկ անգամ,
և միայն մեկ գործակալ։

Քանի դեռ սկզբնական վիճակը հայտնի է որպես միանշանակ, և բոլոր գործողությունները վճռորոշ են, աշխարհի վիճակը ցանկացած հաջորդականության գործողությունից հետո հնարավոր է ճշգրիտ կանխատեսել, իսկ մանրամասները նկատելու ունակության հարցը անտեղի է դասական պլանավորման համար։

Բացի այդ, պլանները կարող են սահմանվել որպես գործողությունների հաջորդականություն, քանի որ միշտ էլ նախապես հայտնի է, թե որ գործողություններն անհրաժեշտ կլինեն։

Ոչ վճռորոշ գործողություններով կամ գործակալի վերահսկողությունից դուրս այլ իրադարձություններով, հնարավոր գործողությունները ձևավորում են ծառ, իսկ պլանները պետք է որոշեն համապատասխան գործողություններ ծառի յուրաքանչյուր ճյուղի համար։

Դիսկրետ-ժամանակ Մարկովի որոշումների կայացման գործընթացները (MDP)^[2] պլանավորում են խնդիրներ կապված.^[3]

անժամկետ գործողությունների,
ոչ վճռորոշ գործողություններ պատահականությամբ,
լիարժեք դիտողականություն,
պարգևատրման գործառույթի առավելագույն մեծացում,
և մեկ գործակալ։

Երբ ամբողջական դիտողականությունը փոխարինվում է մասնակի դիտողականությամբ, պլանավորումը համապատասխանում է Մարկովի որոշման մասնակիորեն դիտարկելի գործընթացին (POMDP):

Եթե կան մեկից ավելի գործակալներ, մենք ունենք բազմաագենտային պլանավորում, որը սերտորեն կապված է խաղերի տեսության հետ։

Ոլորտից անկախ պլանավորում^[4]

ԱԻ-ի պլանավորման մեջ պլանավորողները սովորաբար մուտքագրում են ոլորտի մոդելը (ոլորտի մոդելի հնարավոր գործողութունների բազմությունը) ինչպես նաև հատուկ խնդիրը՝ լուծելու որոշված նախնական պայմանով և նպատակով, ի տարբերություն նրանց, որոնցում չկա ոլորտի մուտքագրում։ Այդ պլանավորողները կոչվում են «ոլորտից անկախ»` շեշտը դնելով այն փաստի վրա, որ նրանք կարող են լուծել պլանավորման խնդիրները օգտվելով լայն ոլորտներից։ Ոլորտների բնորոշ օրինակներն են ՝ բլոկների դասավորումը, բարդ գործողությունների մանրամասն կազմակերպումն ու իրականացումը, աշխատանքային հոսքի կառավարումը և ռոբոտների առաջադրանքների պլանավորումը։ Հետևաբար, մեկ ոլորտի անկախ պլանավորողը կարող է օգտագործվել այս բոլոր տարբեր ոլորտների պլանավորման խնդիրները լուծելու համար։ Մյուս կողմից, արմատական պլանավորողը բնորոշ է հատուկ ոլորտի պլանավորողին։

Ոլորտի մոդելավորող լեզուների պլանավորում^[5]

Ոլորտների պլանավորման և հատուկ պլանավորման ծնդիրների ներկայացման առավել հաճախ պգտագործվող լեզուները, ինչպիսիք են Stanford Research Institute Problem Solver և Planning Domain Definition Language դասական պլանավորման համար, հիմնված են վիճակի փոփոխականի^[6] վրա։ Աշխարհի ցանկացած հնարավոր վիճակ վիճակի փոփոխականի արժեքների վերագրելիքն է, և գործողությունները որոշում են, թե ինչպես են փոփոխվում վիճակի փոփոխականների արժեքները, երբ այդ գործողությունն իրականանում է։

Պլանավորման խնդիրները նկարագրելու այլընտրանքային լեզու է [./Https://en.wikipedia.org/wiki/Hierarchical%20task%20network հիերարխիկ առաջադրանքների ցանցերը]^[7], որոնցում տրված է մի շարք առաջադրանքներ, և յուրաքանչյուր խնդիր կարող է իրականացվել կամ պրիմիտիվ գործողությամբ կամ վերածվել մի շարք այլ խնդիրների։ Պարտադիր չէ, որ սա պարունակի վիճակի փոփոխականներ, չնայած ավելի իրատեսական կիրառություններում վիճակի փոփոխականները պարզեցնում են առաջադրանքի ցանցերի նկարագրությունը։

Ծանոթագրություններ

↑ Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automated Planning: Theory and Practice, Morgan Kaufmann, ISBN 1-55860-856-7
↑ ^2,0 ^2,1 «Automated Planning: Theory and Practice». www.cs.umd.edu. Վերցված է 2019 թ․ հոկտեմբերի 20-ին.
↑ «Automated Planning» (PDF).
↑ «Towards learning domain-independent planning heuristics».
↑ «Automated planning and scheduling» (անգլերեն). 2019 թ․ սեպտեմբերի 13. {{cite journal}}: Cite journal requires |journal= (օգնություն)
↑ «State variable» (անգլերեն). 2019 թ․ հունվարի 31. {{cite journal}}: Cite journal requires |journal= (օգնություն)
↑ «Hierarchical task network» (անգլերեն). 2019 թ․ մարտի 11. {{cite journal}}: Cite journal requires |journal= (օգնություն)

Գրականություն

Automated Planning - Alessandro Cimatti, Marco Pistore, Paolo Traverso
USING ARTIFICIAL INTELLIGENCE TECHNIQUES FOR AUTOMATED PLANNING AND SCHEDULING - Raymond E. Levitt1, John C. Kunz2, and Nabil A. Kartanr3
Automated Scheduling and Planning: From Theory to Practice - Ender Ozcan
Intelligent Scheduling - Monte Zweben
Planning with Markov Decision Processes: An AI Perspective Mausam - Planning with Markov Decision Processes: An AI Perspective Mausam

Արտաքին հղումներ

[1] Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automated Planning: Theory and Practice, Morgan Kaufmann, ISBN 1-55860-856-7

[cs.umd.edu-2] 2,0 ^2,1 «Automated Planning: Theory and Practice». www.cs.umd.edu. Վերցված է 2019 թ․ հոկտեմբերի 20-ին.

[3] «Automated Planning» (PDF).

[4] «Towards learning domain-independent planning heuristics».

[5] «Automated planning and scheduling» (անգլերեն). 2019 թ․ սեպտեմբերի 13. {{cite journal}}: Cite journal requires |journal= (օգնություն)

[6] «State variable» (անգլերեն). 2019 թ․ հունվարի 31. {{cite journal}}: Cite journal requires |journal= (օգնություն)

[7] «Hierarchical task network» (անգլերեն). 2019 թ․ մարտի 11. {{cite journal}}: Cite journal requires |journal= (օգնություն)

[1]

[2]

[3]

[4]

[5]

[6]

[7]