{"id":684,"date":"2018-05-26T22:00:36","date_gmt":"2018-05-26T22:00:36","guid":{"rendered":"https:\/\/my.dev.vanderbilt.edu\/cs4260cs5260\/?page_id=684"},"modified":"2018-09-04T12:43:10","modified_gmt":"2018-09-04T12:43:10","slug":"propositional-planning-with-certainty-scenarios","status":"publish","type":"page","link":"https:\/\/my.dev.vanderbilt.edu\/cs4260cs5260\/propositional-planning-with-certainty-scenarios\/","title":{"rendered":"Propositional Planning with Certainty Scenarios"},"content":{"rendered":"

An example of an AI planner definition<\/strong><\/p>\n

Step 1: you have to represent operators and states, including goal and start states<\/p>\n

A)<\/strong>\u00a0For purposes of this specification, a course<\/strong> is represented by two strings (<program>, <designation>), such as (\u201cCS\u201d \u201c4260\u201d), (\u201cCS\u201d \u201c3265\u201d), (\u201cHIST\u201d \u201c2640\u201d), (\u201cCHEM\u201d, \u201c3135W\u201d).<\/p>\n

B)<\/strong>\u00a0Each course is associated with a course description<\/strong>, which for purposes of this specification, is limited to number of credits, terms in which the course is offered, and prerequisites of the course. For example, the description of\u00a0(\u201cCS\u201d, \u201c4260\u201d)<\/strong>\u00a0is\u00a0((\u201cCS\u201d, \u201c4260\u201d), 3, (\u201cFall\u201d), [[(\u201cCS\u201d, \u201c3250\u201d) and (\u201cCS\u201d, \u201c3251\u201d)]])<\/strong>, and the description of\u00a0(\u201cCS\u201d, \u201c1101\u201d)<\/strong>\u00a0is\u00a0((\u201cCS\u201d, \u201c1101\u201d), 3, (\u201cFall\u201d, \u201cSpring\u201d), [ ])<\/strong>.<\/p>\n

C)<\/strong>\u00a0A\u00a0scheduled term<\/strong>\u00a0is represented by a pair of strings, such as (\u201cFall\u201d, \u201cFrosh\u201d), (\u201cSpring\u201d, \u201cSoph\u201d), (\u201cFall\u201d, \u201cJunior\u201d), and (\u201cSpring\u201d, \u201cSenior\u201d).\u00a0This spec won’t\u00a0create a schedule for specific years (e.g., 2012 \u2013 2016), but for frosh-senior (or less, if the requirements can be completed in less than 4 years).<\/p>\n

D)<\/strong>\u00a0A\u00a0scheduled course<\/strong>\u00a0is a triple containing a course, a scheduled term, and a number of credits, such as ((\u201cCS\u201d, \u201c2201\u201d), (\u201cSpring\u201d, \u201cFrosh\u201d), 3).<\/p>\n

E)<\/strong>\u00a0There are\u00a0higher level requirements<\/strong>\u00a0for different majors and minors too, which are also represented by a pair of strings, such as (\u201cCS\u201d, \u201cmathematics\u201d), which represents the mathematics requirements for a CS major.<\/p>\n

Records for higher level requirements are also be stored in the\u00a0course_descriptions\u00a0<\/strong>dictionary (the list of all courses), but there these requirements can be completed (in theory) during any term, and these higher level requirements add 0 (zero) additional credits beyond the course credits. So, for example, the \u201ccourse\u201d\u00a0description representing the higher level requirement<\/strong>\u00a0(\u201cCS\u201d, \u201cmathematics\u201d) is ((\u201cCS\u201d, \u201cmathematics\u201d), 0, (\u201cFall\u201d, \u201cSpring\u201d), \u2026). A\u00a0scheduled course representing a higher level requirement<\/strong>\u00a0might be ((\u201cCS\u201d, \u201cmathematics\u201d), (\u201cFall\u201d, \u201cJunior\u201d), 0).<\/p>\n

F)<\/strong>\u00a0Courses and high level requirements have zero or more listed prerequisites. For example, using a format close to that given in the Vanderbilt course catalog<\/p>\n

1.\u00a0(\u201cCS\u201d, \u201c1101\u201d)<\/strong>\u00a0has no prerequisites.
\n2.\u00a0(\u201cCS\u201d, \u201c3270\u201d)<\/strong>\u00a0has a single listed prerequisite of (\u201cCS\u201d, \u201c2231\u201d).
\n3.\u00a0(\u201cCS\u201d, \u201c4260\u201d)<\/strong>\u00a0has a conjunction of two prerequisites (i.e., [(\u201cCS\u201d, \u201c3250\u201d) and (\u201cCS\u201d, \u201c3251\u201d)]).
\n4.\u00a0(\u201cCS\u201d, \u201c4283\u201d)<\/strong>\u00a0has a disjunction of two prerequisites (i.e., [(\u201cCS\u201d, \u201c3281\u201d) or (\u201cEECE\u201d, \u201c4376\u201d])).
\n5.\u00a0(\u201cCS\u201d, \u201c3258\u201d)<\/strong>\u00a0has a combination of conjunction and disjunction (i.e., [[(\u201cMATH\u201d, \u201c2410\u201d) or (\u201cMATH\u201d, \u201c2400\u201d) or (\u201cMATH\u201d, \u201c2501\u201d) or (\u201cMATH\u201d, \u201c2600\u201d)] and (\u201cCS\u201d, \u201c3251\u201d)]).
\n6.\u00a0(\u201cCS\u201d, \u201cmathematics\u201d)<\/strong>\u00a0has \u201cprerequisites\u201d of [(\u201cCS\u201d, \u201ccalculus\u201d) and (\u201cCS\u201d, \u201cstats-probability\u201d) and (\u201cCS\u201d, \u201cmath-elective\u201d)].
\n7. In turn,\u00a0(\u201cCS\u201d, \u201ccalculus\u201d)<\/strong>\u00a0has prerequisites that are stated as
\n[ [(\u201cMATH\u201d, \u201c1200\u201d) and (\u201cMATH\u201d, \u201c1201\u201d) and (\u201cMATH\u201d, \u201c1301\u201d) and (\u201cMATH\u201d, \u201c2300\u201d)] and [(\u201cMATH\u201d, \u201c2410\u201d) or (\u201cMATH\u201d, \u201c2600\u201d)]]
\nor
\n[[ (\u201cMATH\u201d, \u201c1300\u201d) and (\u201cMATH\u201d, 1301) and (\u201cMATH\u201d, \u201c2300\u201d)] and [(\u201cMATH\u201d, \u201c2410\u201d) or (\u201cMATH\u201d, \u201c2600\u201d)]]
\nor
\n[(\u201cMATH\u201d, \u201c1300\u201d) and (\u201cMATH\u201d, \u201c1301\u201d) and (\u201cMATH\u201d, \u201c2500\u201d) and (\u201cMATH\u201d, \u201c2501\u201d)]
\n8.\u00a0(\u201cCS\u201d, \u201cmajor\u201d)<\/strong>\u00a0has prerequisites
\n[(\u201cCS\u201d, \u201cmathematics\u201d) and (\u201cCS\u201d, \u201cscience\u201d) and (\u201cES\u201d, \u201c1401\u201d) and (\u201cES\u201d, \u201c1402\u201d) and (\u201cES\u201d, \u201c1403\u201d) and (\u201cEng\u201d, \u201cliberalartscore\u201d) and (\u201cCS\u201d, \u201ccore\u201d) and (\u201cCS\u201d, \u201cdepth\u201d) and (\u201cCS\u201d, \u201c4959\u201d) and (\u201cCS\u201d, \u201ctechnicalelectives\u201d) and (\u201cCS\u201d, \u201copenelectives\u201d) and (\u201cCS\u201d, \u201cwritingrequirement\u201d)]<\/p>\n

G)<\/strong>\u00a0Each requirement\u2019s prerequisites will be provided in\u00a0disjunctive normal form<\/strong>, given as a list of lists of subordinate requirements. For example,
\n1. the (\u201cCS\u201d, \u201ccalculus\u201d) prerequisites will actually be given to the planner as
\n[ [(\u201cMATH\u201d, \u201c1200\u201d) and (\u201cMATH\u201d, \u201c1201\u201d) and (\u201cMATH\u201d, \u201c1301\u201d) and (\u201cMATH\u201d, \u201c2300\u201d) and (\u201cMATH\u201d, \u201c2410\u201d)]
\nor [(\u201cMATH\u201d, \u201c1200\u201d) and (\u201cMATH\u201d, \u201c1201\u201d) and (\u201cMATH\u201d, \u201c1301\u201d) and (\u201cMATH\u201d, \u201c2300\u201d) and (\u201cMATH\u201d, \u201c2600\u201d)]
\nor [(\u201cMATH\u201d, \u201c1300\u201d) and (\u201cMATH\u201d, \u201c1301\u201d) and (\u201cMATH\u201d, \u201c2300\u201d) and (\u201cMATH\u201d, \u201c2410\u201d) ]
\nor [(\u201cMATH\u201d, \u201c1300\u201d) and (\u201cMATH\u201d, \u201c1301\u201d) and (\u201cMATH\u201d, \u201c2300\u201d) and (\u201cMATH\u201d, \u201c2600\u201d) ]
\nor [(\u201cMATH\u201d, \u201c1300\u201d) and (\u201cMATH\u201d, \u201c1301\u201d) and (\u201cMATH\u201d, \u201c2500\u201d) and (\u201cMATH\u201d, \u201c2501\u201d)] ]<\/p>\n

Because the \u2018or\u2019s and \u2018and\u2019s are implicit in the nesting of a DNF structures, we can simply with this as a list of lists, without the logical keywords. So, the\u00a0abbreviated DNF\u00a0<\/strong>representation of the (\u201cCS\u201d, \u201ccalculus\u201d) prerequisites can be written as<\/p>\n

[ [(\u201cMATH\u201d, \u201c1200\u201d), (\u201cMATH\u201d, \u201c1201\u201d), (\u201cMATH\u201d, \u201c1301\u201d), (\u201cMATH\u201d, \u201c2300\u201d), (\u201cMATH\u201d, \u201c2410\u201d)]
\n, [(\u201cMATH\u201d, \u201c1200\u201d), (\u201cMATH\u201d, \u201c1201\u201d), (\u201cMATH\u201d, \u201c1301\u201d), (\u201cMATH\u201d, \u201c2300\u201d), (\u201cMATH\u201d, \u201c2600\u201d)]
\n, [(\u201cMATH\u201d, \u201c1300\u201d), (\u201cMATH\u201d, \u201c1301\u201d), (\u201cMATH\u201d, \u201c2300\u201d), (\u201cMATH\u201d, \u201c2410\u201d) ]
\n, [(\u201cMATH\u201d, \u201c1300\u201d), (\u201cMATH\u201d, \u201c1301\u201d), (\u201cMATH\u201d, \u201c2300\u201d), (\u201cMATH\u201d, \u201c2600\u201d) ]
\n, [(\u201cMATH\u201d, \u201c1300\u201d), (\u201cMATH\u201d, \u201c1301\u201d), (\u201cMATH\u201d, \u201c2500\u201d), (\u201cMATH\u201d, \u201c2501\u201d) ] ]<\/p>\n

ii) The (\u201cCS\u201d, \u201c3258\u201d) prerequisites in DNF would be given as
\n[ [(\u201cMATH\u201d, \u201c2400\u201d), (\u201cCS\u201d, \u201c3251\u201d)],
\n[(\u201cMATH\u201d, \u201c2501\u201d), (\u201cCS\u201d, \u201c3251\u201d)],
\n[(\u201cMATH\u201d, \u201c2600\u201d), (\u201cCS\u201d, \u201c3251\u201d)] ]<\/p>\n

iii) The (\u201cCS\u201d, \u201c4260\u201d) prerequisites would be given as [ [(\u201cCS\u201d, \u201c3250\u201d), (\u201cCS\u201d, \u201c3251\u201d)] ] (i.e., a disjunctive statement with only one conjunctive element)<\/p>\n

iii) The (\u201cCS\u201d, \u201c4283\u201d) prerequisites would be given as [ [(\u201cCS\u201d, \u201c3281\u201d)], [(\u201cEECE\u201d, \u201c4376\u201d)] ] (i.e., a disjunction of two one-element conjunctions)<\/p>\n

iv) The (\u201cCS\u201d, \u201c3270\u201d) prerequisites are [ [(\u201cCS\u201d, \u201c2231\u201d)] ]<\/p>\n

v) The (\u201cCS\u201d, \u201c1101\u201d) prerequisites are [ ]<\/p>\n

H)<\/strong>\u00a0Each\u00a0state<\/strong>\u00a0in the state space of the regression planner is a\u00a0conjunction<\/strong><\/em>\u00a0of courses and\/or higher-level requirements, such as
\n[ (\u201cCS\u201d, \u201c2201\u201d) and \u2026 and (\u201cCS\u201d, \u201ctechnicalelectives\u201d) and \u2026 and
\n(\u201cMATH\u201d, \u201c2410\u201d) ]
\nor written in strict list form as
\n[ (\u201cCS\u201d, \u201c2201\u201d), \u2026, (\u201cCS\u201d, \u201ctechnicalelectives\u201d), \u2026, (\u201cMATH\u201d, \u201c2410\u201d) ]
\nIn a regression planner, this represents a set of conditions (subgoals) that are to be achieved<\/p>\n

I)<\/strong>\u00a0The\u00a0initial state<\/strong>\u00a0for the regression planner, an argument to the\u00a0course_scheduler\u00a0<\/strong>function, are the courses for which a student already has credit when the planner is executed. Formally, this is a\u00a0conjunction<\/strong><\/em>\u00a0of courses. For this specification assume that the initial state does not include higher level requirements. For example, a student with AP credit for introductory Spanish and introductory programming, would have an initial state of [(\u201cSPAN\u201d, \u201c1101\u201d), (\u201cCS\u201d, \u201c1101\u201d)]. Note that the initial state is not the same as the start state (or start node or root of the search tree) of the regression planner \u2014 see section 6.3 of the textbook for clarity on the meaning of terms.<\/p>\n

J)<\/strong>\u00a0Goal conditions<\/strong>, an argument to the\u00a0course_scheduler<\/strong>\u00a0function, indicates specific courses and higher-level requirements that the student wants to satisfy. In a curriculum planner, these would typically correspond to the requirements of one or more majors (and minors), but the goal specification could be composed of any courses and high level requirements. For this specification, assume that the goal conditions are given as a\u00a0conjunction<\/strong><\/em>\u00a0of courses and\/or higher level requirements.
\nFor example, the goal specification for a CS student in the Engineering School, who wanted to double major in biological sciences, and wanted to be be sure to have the AI project course and science fiction, might be<\/p>\n

[(\u201cCS\u201d, \u201cmajor\u201d), (\u201cBSCI\u201d, \u201cmajor\u201d), (\u201cCS\u201d, \u201c4269\u201d), (\u201cENGL\u201d, \u201c3728W\u201d)]<\/p>\n

K)<\/strong>\u00a0Each\u00a0operator<\/strong>, O, has the form\u00a0((PRE(O), EFF(O)), ScheduledTerm, credits)<\/strong>, where\u00a0EFF(O)<\/strong>\u00a0is a single course that will be added to the student\u2019s transcript if the\u00a0conjunction<\/strong><\/em>\u00a0of prerequisite courses in\u00a0PRE(O)<\/strong>\u00a0are satisfied. When an operator is added by the regression planner it will also have a scheduled term associated with it (e.g., (Fall, Senior) and the number of credits that are added).<\/p>\n

L)<\/strong>\u00a0During planning, the system will instantiate the operator template (which you will define in your Python implementation) to construct actual operators based on information about the prerequisites of courses and the terms they are to be taken.
\nSo, for example, an operator for adding (\u201cCS\u201d, \u201c4260\u201d) to the schedule might be
\n([(\u201cCS\u201d, \u201c3250\u201d), (\u201cCS\u201d, \u201c3251\u201d)], (\u201cCS\u201d, \u201c4260\u201d), (\u201cSpring\u201d, \u201cJunior\u201d), 3)<\/strong>.
\nAn operator for adding (\u201cCS\u201d, \u201c1101\u201d) to the schedule might be
\n([ ], (\u201cCS\u201d, \u201c1101\u201d), (\u201cFall\u201d, \u201cFROSH\u201d), 3)<\/strong>.
\nFor an operator that expands a higher level requirement<\/p>\n

M)<\/strong>\u00a0A\u00a0plan<\/strong>\u00a0is a\u00a0conjunction<\/strong><\/em>\u00a0of scheduled courses, with constraints that (a) the sum of the credits in each scheduled term (e.g., (\u201cSpring\u201d, \u201cSoph\u201d)) must not be less than 12 and must not be greater than 18.; and (b) no course can be planned for a term that occurs before the term that a pre-requisite is planned.<\/p>\n

N)<\/strong>\u00a0If the conditions of the goal cannot be satisfied in four years under the constraints above, then the scheduler should return ( ) \u2014 the empty conjunction<\/p>\n

Q)<\/strong>\u00a0There are other characteristics of your planner that we will measure, such as the length of plans on sample problems<\/p>\n

R)<\/strong>\u00a0Again, your implementation is to be a (heuristic) depth-first, regression planner that adheres to the def course_scheduler (course_descriptions, goal_conditions, initial_state) at the top level. But you have considerable freedom in designing the system, to include class definitions that are used internally by your system. For example, if you aspire to implement composite (macro) learning if a subsequent implementation, you could define the EFFects list of operators as a list of courses rather than a single course INTERNALLY, even if on your initial submission will assume that a plan of operators is produced with a singleton EFFect for each operator.
\nWhatever your design, it should adhere roughly to the implementation of the generic search algorithm of Section 3.4 (http:\/\/artint.info\/2e\/html\/ArtInt2e.Ch3.S4.html<\/a>) as a depth-first search, and a backward or regression search implementation of a scheduler, as addressed in sections 3.8.2 (http:\/\/artint.info\/2e\/html\/ArtInt2e.Ch3.S8.SS2.html<\/a>) and 6.3 (http:\/\/artint.info\/2e\/html\/ArtInt2e.Ch6.S3.html).<\/p>\n

\"Illustration<\/a>

Illustration of search space — a plan is created by reading operators along a path from a leaf to the root<\/p><\/div>\n

Learning Macros<\/h2>\n

In scheduling for many students, a learning scheduler might observe that to meet objectives to satisfy a major\u2019s requirements in four years, there are some courses that need to be scheduled in close proximity of each other. These courses can packaged as a \u201cmacro\u201d (Chapter 6) and inserted into schedule as a package during planning. In fact, it is almost certainly the case that such macros can be discovered \u201canalytically\u201d by scheduling for one or a few \u201cgeneric\u201d students in which the minimum 12 hour credit per term is dropped. There are analytic approaches to machine learning, like this, that don\u2019t require substantial data.<\/p>\n","protected":false},"excerpt":{"rendered":"

An example of an AI planner definition Step 1: you have to represent operators and states, including goal and start states A)\u00a0For purposes of this specification, a course is represented by two strings (<program>, <designation>), such as (\u201cCS\u201d \u201c4260\u201d), (\u201cCS\u201d … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":633,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-684","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/my.dev.vanderbilt.edu\/cs4260cs5260\/wp-json\/wp\/v2\/pages\/684","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/my.dev.vanderbilt.edu\/cs4260cs5260\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/my.dev.vanderbilt.edu\/cs4260cs5260\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/my.dev.vanderbilt.edu\/cs4260cs5260\/wp-json\/wp\/v2\/users\/633"}],"replies":[{"embeddable":true,"href":"https:\/\/my.dev.vanderbilt.edu\/cs4260cs5260\/wp-json\/wp\/v2\/comments?post=684"}],"version-history":[{"count":6,"href":"https:\/\/my.dev.vanderbilt.edu\/cs4260cs5260\/wp-json\/wp\/v2\/pages\/684\/revisions"}],"predecessor-version":[{"id":789,"href":"https:\/\/my.dev.vanderbilt.edu\/cs4260cs5260\/wp-json\/wp\/v2\/pages\/684\/revisions\/789"}],"wp:attachment":[{"href":"https:\/\/my.dev.vanderbilt.edu\/cs4260cs5260\/wp-json\/wp\/v2\/media?parent=684"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}