算法代写 | CS 3346a — CS 3121a Assignment 2

1. Consider the Constraint Satisfaction Problem (CSP) expressed as the constraint graph given in the lecture slides labelled at the bottom of the slides as D. Poole and A. Mackworth 2009 Artificial Intelligence Lecture 4.3, Page 7. It has been made Arc Consistent on the slide labelled Lecture 4.3, Page 8. The result of the first recursive descent into the variable elimination algorithm is given on the slide labelled Lecture 4.3, Page 9. The resulting constraint graph is given on the slide labelled Lecture 4.3, Page 10.

(a)  How many leaf nodes are there in the Generate and Test tree for the original problem (Lecture 4.3, Page 7). Show how you computed this answer.

(b)  How many leaf nodes are there in the Generate and Test tree for the arc consistent problem (Lecture 4.3, Page 8). Show how you computed this answer.

(c)  The first iteration of the variable elimination algorithm has been provided. Show how the variable elimination algorithm gives the solutions for this CSP. Eliminate the variables in the following order: D, E, B. Your answer must show the new relations generated by the algorithm when descending in the recursion and the relations that are generated when ascending. Marks will be given for each of these elements of your answer.

(d)  With the constraint graph in part (b) above (the graph representing the CSP that has been preprocessed by AC-3), show how backtracking search can be used to solve this problem. To do this, you must draw the search tree generated to find all answers. Each node in the tree represents a choice of a domain element for the variable represented by the level of the tree. Label the tree with a ‘×’ underneath paths that can be cutoff together with the constraint that caused the cutoff. The first such cutoff is shown below. Use the following variable ordering: A, B, D, E, and C. Indicate (in a summary) the valid solution(s) that is (are) found.

2. Show the search tree produced by a regression planner using a breadth-first search for the following planning problem.

Fluents to describe states

RLoc: Rob’s location (has 3 values: Lab, CS, Off)

RHC: Rob has coffee (boolean)

SWC: Sam wants coffee (boolean)

Here is a map describing the robot’s world (i.e. the connected locations):

Lab – CS – Off

Goal state: ¬SWC

Here is the PDDL representation of the actions:

move (loc1, loc2) precondition: RLoc(loc1) ∧

Connected(loc1, loc2) effect: ¬RLoc(loc1) ∧ RLoc(loc2)

puc %Comment: pickup coffee precondition: ¬RHC ∧ RLoc(CS) effect: RHC

dc %Comment: deliver coffee precondition: RHC ∧ RLoc(Off) effect: ¬SWC ∧ ¬RHC

On the search tree, label each arc with the action instance. Each node in the search tree must indicate the goal represented by the node. Be certain to complete all possible branches on the final (successful) level of the tree.

HINTS:

1. (a)  Apply the CWA to the initial state to obtain some important negations.
2. (b)  Remember the Unique Names Assumption.
3. (c)  Pruning 1: Prune any path whose current node to be expanded represents a goal that entails a goal found in a node at the current level or above in the tree.
4. (d)  Pruning 2: In addition to the normal breadth-first search pruning (Pruning 1), prune any path whose current node to be expanded contains a non-fluent (i.e., a Connected predicate) that is inconsistent with the initial state, or contains an inconsistent goal (e.g., the robot cannot be in different locations at the same time). E-mail: [email protected]  微信:dmxyzl003 