cps721: Assignment 5 (100 points).
Due date: Electronic file – Monday, November 29, 2021, before 17:00. You have to work in groups of TWO, or THREE. You cannot work alone.
YOU SHOULD NOT USE ”;” , ”!” AND ”–>” IN YOUR PROLOG RULES.
You can discuss this assignment only with your CPS721 group or with the CPS721 instructor. You cannot use any external resources (including those which are posted on the Web) to complete this assignment. Failure to do this will have negative effect on your mark. By submitting this assignment you acknowledge that you read and under- stood the course Policy on Collaboration in homework assignments stated in CPS721 course management form.
Copyright By PowCoder代写 加微信 powcoder
This assignment will exercise what you have learned about problem solving and planning using Prolog. More specifically, in this assignment, you are asked to solve planning problems using the situations and fluents approach. For each of Parts 1 and 2, you should use a file containing the rules for solve problem, reachable, max length(List,Bound) as explained in class, and then add your own precondition and successor state axioms using terms and predicates specified in the assignment. (Download the planner from the Assignments page). 1
1 (65 points). There is a common household refrigerator with an old broken compressor, and the goal is to replace an old compressor with a new one. The compressor is covered with a backplane. The backplane is being held in place with a few bolts that are initially screwed into the backplane. To repair a broken compressor, one has to unfasten all bolts, turn the fridge off to prevent electric shock, remove a backplane that covers the broken compressor, then change the compressor, attach a backplane to make sure it is in place, fasten all bolts, and turn the fridge on. We would like to solve this planning problem using an approach considered in class. Specifically, you have to take the generic planner written in Prolog, but you have to provide missing rules as explained below. There are the following actions in this application domain. (Recall that actions are terms: they can be only arguments of predicates or equality.)
• fasten(Bolt,Backplane): fasten Bolt, provided Bolt holds Backplane and it is not screwed yet to Backplane in situation S.
• unfasten(Bolt,Backplane):thisactionwillundotheeffectsofthefastenaction.Itispossibletoexecutethisactionif Bolt holds Backplane and it is currently screwed into backplane.
• remove(Backplane, F ridge): remove Backplane from F ridge. This is possible if Backplane is a part of F ridge, Backplane is in place in current situation S, if Fridge is not turned on, and there exists no bolt holding Backplane such that it is screwed into Backplane in S.
• attach(Backplane,Fridge):attachBackplanetoFridge,providedBackplaneisapartofFridgethatisnotinplace in current situation S, F ridge is not turned on in S, and all bolts holding the backplane are not screwed to the backplane in S. (The last condition on bolts being unscrewed is same as for the previous action, but it is worded differently.)
• start(Fridge,Backplane): plug Fridge with Backplane to electrical socket to turn it on and undo the effect of the opposite action stop(F ridge). This action is possible if Backplane that is a part of F ridge is in place in S, the fridge is currently not turned on in S, and there exists no bolt holding the backplane that is currently not screwed to the backplane in S. In other words, all bolts must be screwed into the backplane before the fridge can be started.
• stop(Fridge) action is opposite to the previous one; this action can be executed only if Fridge is powered on in S.
• change(Old,New,Backplane): replace an Old compressor with a New compressor. This is possible if Backplane covering Old is currently not in place in S, Old compressor is attached in S, but New compressor is not attached in S. After replacing, New will be attached instead of Old.
There are several auxiliary predicates that are not fluents: their truth values do not change after executing any of the actions. In particular, compressor(X) means that X is a compressor, partOf(P,F) means that backplane P is part of a fridge F, holds(B, P ) means that a bolt B is one of the bolts that hold a backplane P . These predicates do not change from one situation to another. To represent features of this domain that can change, it is sufficient to introduce the following predicates with situation argument (fluents). Recall that fluents are predicates with a situation S as the last argument, where situations are represented by lists of actions that have been already executed.
1 This is not directly related to the assignment, but out of curiosity, you might wish to watch a 4min episode about the crow who can solve a difficult problem solving task that requires 8 steps: https://www.youtube.com/watch?v=AVaITA7eBZE This episode is taken the recent BBC 2 series “Inside the Animal Mind”.
• screwed(Bolt, Blackplane, S): Bolt is screwed into Blackplane in S after executing a fastening action. All screwed bolts remain screwed after any action unless the agent unfastens them.
• inP lace(Backplane, S): Backplane is in place in S after attaching it to the fridge (by default, there is only one fridge). A backplane remains in place unless it is removed from the fridge.
• turnedOn(Fridge,S): Fridge is turned on in a situation S. A fridge remains turned on no matter what actions are subsequently executed, unless it is stopped.
• attached(Compressor, S): Compressor is attached (to the single available fridge), in S. It remains attached unless it is replaced with another compressor.
• covers(Backplane,Compressor,S): Backplane serves as cover for a new Compressor in the current situation S. This fluent becomes true after replacing an old compressor with a new Compressor. A Backplane remains to serve as cover for Compressor in the next situation unless this compressor is replaced with a another one. Note that even if Backplane is chosen to serve as cover for Compressor, Backplane can be in place or not in place in S, depending on whether Backplane was attached, or removed, respectively. In other words, this fluent links a Backplane and a Compressor.
Before you can solve planning problems in this domain, you have to write precondition axioms and successor state axioms. Write all your Prolog rules in the file fridge.pl provided for you.
Consider the following initial and goal situations:
compressor(c1). compressor(c2). partOf(p1,f1). % backplane p1 is part of fridge f1 % holds(b1,p1). holds(b2,p1). % bolts b1 and b2 hold backplane p1 %
/* the following fluents are true initially */
inPlace(p1,[]). attached(c1,[]). % compressor c1 is attached and p1 is in place % covers(p1,c1,[]). turnedOn(f1,[]). % backplane p1 serves to cover compressor c1 % screwed(b1,p1,[]). screwed(b2,p1,[]). % backplane p1 is screwed with bolts b1 and b2 %
/* In the goal state, another compressor is attached and the fridge is turned on. */ goal_state(S) :- attached(c2,S), turnedOn(f1,S).
1. Download the file initFridge.pl with descriptions of the initial and goal states from the Assignments Web page. Keep both this file and the file fridge.pl in the same folder. When ECLiPSe Prolog compiles the file fridge.pl it loads the file initFridge.pl automatically. Do not copy content of initFridge.pl into your file fridge.pl because a TA will use other initial and goal states to test your program in fridge.pl Solve this simple planning problem using the planner with the upper bound 9 on the number of actions. It should take a few seconds or less for your planner to solve this problem (less than 1 minute even if your CPU is very slow). If you would like to debug your program, you can try a simpler goal state (e.g., when only the backplane p1 is not in place, this needs 4 actions only). Request several plans using ”;” command. Discuss briefly your results in the file fridge.txt
2. The predicate useless(A,ListOfPastActions) is true if an action A is useless given the list of previously exe- cuted actions. The predicate useless(A,ListOfPastActions) helps to solve the planning problem by providing declarative heuristics (advises) to the planner. If this predicate is correctly defined using a few rules (one or more rules per action A), then it helps to speed-up the search that your program is doing to find a list of actions solving a problem. Write at least 5 rules that define this predicate: think about useless repetitions you would like to avoid, and about order of execution (i.e., use common sense properties of the application domain). Keep these new rules in the same file fridge.pl Your rules have to be general enough to be applicable to any fridge domain as outlined above. In other words, they have to help in solving a planning problem for any instance (i.e., any initial and goal states), not just those which are given to you. Once you have wrote rules for useless(A,ListOfPastActions), test them using same planning problem as above (that takes 9 actions to solve), or any similar simple problems. You have to use the following rule for the predicate reachable(S,Plan) when you do these tests:
reachable(S2, [M | ListOfActions]) :- reachable(S1,ListOfActions), legal_move(S2,M,S1),
not useless(M,ListOfActions).
Notice if solving planning problems takes more time or less time. Explain why. Include your testing results and a brief discussion of your results in the report fridge.txt
3. Finally, consider a variation of the planning problem given above, when the fridge needs 3 bolts, or 4 bolts instead of 2 bolts. Each time add a pair of the corresponding atomic statements to describe another initial state, e.g., for the case when a backplane needs 3 bolts, add
holds(b3,p1). screwed(b3,p1,[]).
Keep the same goal state as above, and compare the running time required in this case to the running time taken by the planner when you had 2 bolts only. Do similar modification and comparison when the fridge needs 4 bolts. Save your program where a backplane needs 4 bolts in the file fridge4bolts.pl This file must include all declarative heuristics (i.e., rules defining the predicate useless(M,ListOfActions)), precondition axioms, successor state axioms, as well as the elaborated initial state description. It should take less than 1 minute for your planner to solve this problem (time depends on speed of your CPU). Notice if solving planning problems takes more time or less time in comparison to the case when there are 2 bolts only. Explain why. Include your testing results and a brief discussion of your results in the report fridge.txt If you program does work fast (i.e., it computes a plan in less than 1 minute), then try also the case when the fridge needs 5 bolts. Write in your report what happens in this case.
Handing in solutions: An electronic copy of your files fridge.pl and fridge4bolts.pl as well as a copy of fridge.txt must be included in your zip archive. The file fridge.txt must include a copy of session(s) with Prolog, showing the queries you submitted and the answers returned. Write also what computer (manufacturer, CPU, memory) you use to solve this planning problem.
2 (35 points). The application domain in this question is motivated by the Rover missions. The objective is to use a collection of mobile rovers equipped with different, but possibly overlapping, sets of equipment to gather data. The rovers must travel between way-points on a planet surface, carrying out a variety of data-collection missions and transmitting data back to a lander. The traversal is complicated by the fact that certain rovers are restricted to traveling over certain terrain types and this makes particular routes impassable to some of the rovers.
We consider below terms (actions) and predicates (fluents) that are general enough to deal with any collection of entities (rovers, samples, locations). In particular, we consider the following four actions.
• take(Rover,Sample,X)–RovercantakeSampleatthelocationXifitisequippedtotakeSample,Roverislocated at X in S, rover is not full and Sample is available at X (see below how this can be implemented). This action makes the rover’s store full. Assume that all rovers can take only one sample at a time.
• drop(Rover) – Rover makes its store empty by discarding the last sample; this action is possible if Rover’s store is full.
• navigate(Rover, X, Y ) – Rover can travel from a location X to another location Y if it is located at X and it can
traverse a route from X to Y (see below).
• communicate(Rover,Sample,X)–RovercancommunicatedataobtainedfromanalysisofSampletakenatlocation
X to the lander, if Rover is equipped for Sample analysis, and it has data about analysis of Sample from X. We consider the following fluents (predicates with the argument situation).
• hasLander(Loc, Sample, S) – in situation S, the lander received data about Sample taken from a location Loc. This becomes true only if a rover communicates data about Sample to the lander and remains true no matter what actions will be subsequently executed.
• fullStore(Rover,S) – Rover’s store is full in a situation S; this becomes true after taking any sample.
• at(Rover, X, S) – Rover is at a location X in a situation S; this fluent can change only if Rover navigates to another
• hasAnalysis(Rover, Sample, X, S) – in situation S, Rover has analysis of Sample taken at X. This fluent becomes true only if Rover takes Sample at X and remains true unless Rover drops its load or unless Rover communicates analysis of Sample to the lander (i.e., analysis of a sample is removed from the rover’s memory after communicating analysis to the lander and after dropping).
Finally, we consider auxiliary predicates that do not have situational argument (they represent properties that do not change). The ability of individual rovers to traverse between particular pairs of locations is represented by the situation independent predicate canT raverse(Rover, X, Y ). This predicate means that Rover is able to travel between locations X and Y on the surface. There is a finite set of sample types that a rover can take. To account for this, we introduce another situation independent predicate equippedFor(Rover,Sample). This predicate holds if Rover is equipped to take Sample, can do analysis of Sample and can transmit Sample related data to the lander. For example, rovers can sample rocks, soil or take images in different locations near the lander. The predicate availableAt(Sample, X) holds if Sample can be collected at a location X; this predicate is one of the preconditions for the action take(Rover,Sample,X). Note that except these three predicates, all other predicates are fluents, i.e., they have situation argument.
Do the following:
1. Write precondition axioms for all four actions. Recall that to avoid potential problems with negation in Prolog, you should not start bodies of your rules with negated predicates. Make sure that all variables in a predicate are instantiated by constants before you apply negation to the predicate that mentions these variables. Note also that only one sample can be processed by any rover at a time.
2. Writesuccessor-stateaxiomsthatcharacterizehowthetruthvalueofallfluentschangefromthecurrentsituationStothe next situation [A|S]. You will need two types of rules for each fluent: (a) rules that characterize when a fluent becomes true in the next situation as a result of the last action, and (b) rules that characterize when a fluent remains true in the next situation, unless the most recent action changes it to false. ( When you write successor state axioms, you can start bodies of rules with negation of a predicate.) Keep all your rules in the file rovers.pl
3. Consider the following initial and goal configurations:
/* In the initial state, both rovers are at the lander. */ at(r1,lander,[]). at(r2,lander,[]).
canTraverse(r1,lander,bigRock22).
canTraverse(r1,point15,point9).
canTraverse(r2,lander,smallRock7).
canTraverse(r2,point9,bigRock22).
canTraverse(r2,bigRock22,lander).
equippedFor(r1,soilAnalysis).
availableAt(soilAnalysis,point9).
availableAt(rockAnalysis,smallRock7). availableAt(rockAnalysis,bigRock22).
/* Goal: both rocks are sampled and analysis data sent to the lander. */ goal_state(S) :- hasLander(bigRock22,rockAnalysis,S),
hasLander(smallRock7,rockAnalysis,S).
Solve this simple planning problem using the planner with the upper bound 10 on the number of actions. (Download the file that describes this planning problem from the Assignments Web page: the file initRovers.pl). It should take no more than a few seconds for your planner to solve this problem. Do not copy content of initRovers.pl into your file rovers.pl because TA will use other initial and goal states to test your program in rovers.pl Request several plans using ”;” command (keep all plans in your file rovers.txt ). Discuss briefly your results in the file rovers.txt
Handing in solutions:
Electronic copies of your files rovers.pl and rovers.txt must be included in your zip archive.
The file rovers.txt must include a copy of session(s) with Prolog, the query to solve the problem, the computed plans and information about time that your program spent on finding several plans. Write also on what computer (CPU, memory) you solved this planning problem.
3. Bonus work (30 points):
canTraverse(r1,lander,point15).
canTraverse(r1,point9,lander).
canTraverse(r2,lander,point9).
canTraverse(r2,smallRock7,bigRock22).
equippedFor(r2,rockAnalysis).
availableAt(soilAnalysis,point15).
To make up for a grade on another assignment or test that was not what you had hoped for, or simply because you find this area of Artificial Intelligence interesting, you may choose to do extra work on this assignment. Do not attempt any bonus work until the regular part of your assignment is complete. If your assignment is submitted from a group, write whether this bonus question was implemented by all people in your team (in this case bonus marks will be divided evenly between all students) or whether it was implemented by one person only (in this case only this student will get all bonus marks).
Consider the modified version of the generic planner:
reachable(S2, [M | ListOfActions]) :- reachable(S1,ListOfActions), legal_move(S2,M,S1),
not useless(M,ListOfActions).
The predicate useless(A,ListOfActions) is true if an action A is useless given the list of previously performed actions. If this predicate is defined using proper rules, then it helps to speed-up the search that your program is doing to find a list of actions that solves a problem. This predicate provides (application domain dependent) declarative heuristic information about the planning problems that your program solves. The more inventive you are when you implement this predicate, the less search will be required to solve the planning problems. However, any implementation of rules that define this predicate should not use any information related to the specific initial situation. Your rules should be good enough to work with any initial and goal states. When you write rules that define this predicate use common sense properties of the application domain. Write your rules for the predicate useless in the file bonus.pl: it must include the program rovers.pl that you created in Part 2 of this assignment. Write also brief comments to explain your rules. The specification of the goal and initial states must remain in the file initRovers.pl, but you must make appropriate modifications (remove comments, etc) in that file. Once you have the rules for the predicate useless(A,List), solve another planning problem, this time using the modified planner:
/* In the initial state, both rovers are at the lander. */ at(r1,lander,[]). at(r2,lander,[]).
canTraverse(r1,lander,bigRock22).
canTraverse(r1,point15,po
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com