• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# AI lab2 prob1

mrbearp Apr 18th, 2019 (edited) 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import bisect
2.
3. """
4. Defining a class for the problem structure that we will solve with a search.
5. The Problem class is an abstract class from which we make inheritance to define the basic
6. characteristics of every problem we want to solve
7. """
8.
9.
10. class Problem:
11.     def __init__(self, initial, goal=None):
12.         self.initial = initial
13.         self.goal = goal
14.
15.     def successor(self, state):
16.         """Given a state, return a dictionary of {action : state} pairs reachable
17.        from this state. If there are many successors, consider an iterator
18.        that yields the successors one at a time, rather than building them
19.        all at once.
20.
21.        :param state: given state
22.        :return:  dictionary of {action : state} pairs reachable
23.                  from this state
24.        :rtype: dict
25.        """
26.         raise NotImplementedError
27.
28.     def actions(self, state):
29.         """Given a state, return a list of all actions possible
30.        from that state
31.
32.        :param state: given state
33.        :return: list of actions
34.        :rtype: list
35.        """
36.         raise NotImplementedError
37.
38.     def result(self, state, action):
39.         """Given a state and action, return the resulting state
40.
41.        :param state: given state
42.        :param action: given action
43.        :return: resulting state
44.        """
45.         raise NotImplementedError
46.
47.     def goal_test(self, state):
48.         """Return True if the state is a goal. The default method compares
49.        the state to self.goal, as specified in the constructor. Implement
50.        this method if checking against a single self.goal is not enough.
51.
52.        :param state: given state
53.        :return: is the given state a goal state
54.        :rtype: bool
55.        """
56.         return state == self.goal
57.
58.     def path_cost(self, c, state1, action, state2):
59.         """Return the cost of a solution path that arrives at state2 from state1
60.        via action, assuming cost c to get up to state1. If the problem is such
61.        that the path doesn't matter, this function will only look at state2.
62.        If the path does matter, it will consider c and maybe state1 and action.
63.        The default method costs 1 for every step in the path.
64.
65.        :param c: cost of the path to get up to state1
66.        :param state1: given current state
67.        :param action: action that needs to be done
68.        :param state2: state to arrive to
69.        :return: cost of the path after executing the action
70.        :rtype: float
71.        """
72.         return c + 1
73.
74.     def value(self):
75.         """For optimization problems, each state has a value.
76.        Hill-climbing and related algorithms try to maximize this value.
77.
78.        :return: state value
79.        :rtype: float
80.        """
81.         raise NotImplementedError
82.
83.
84. """
85. Definition of the class for node structure of the search.
86. The class Node is not inherited
87. """
88.
89.
90. class Node:
91.     def __init__(self, state, parent=None, action=None, path_cost=0):
92.         """Create node from the search tree,  obtained from the parent by
93.        taking the action
94.
95.        :param state: current state
96.        :param parent: parent state
97.        :param action: action
98.        :param path_cost: path cost
99.        """
100.         self.state = state
101.         self.parent = parent
102.         self.action = action
103.         self.path_cost = path_cost
104.         self.depth = 0  # search depth
105.         if parent:
106.             self.depth = parent.depth + 1
107.
108.     def __repr__(self):
109.         return "<Node %s>" % (self.state,)
110.
111.     def __lt__(self, node):
112.         return self.state < node.state
113.
114.     def expand(self, problem):
115.         """List the nodes reachable in one step from this node.
116.
117.        :param problem: given problem
118.        :return: list of available nodes in one step
119.        :rtype: list(Node)
120.        """
121.         return [self.child_node(problem, action)
122.                 for action in problem.actions(self.state)]
123.
124.     def child_node(self, problem, action):
125.         """Return a child node from this node
126.
127.        :param problem: given problem
128.        :param action: given action
129.        :return: available node  according to the given action
130.        :rtype: Node
131.        """
132.         next_state = problem.result(self.state, action)
133.         return Node(next_state, self, action,
134.                     problem.path_cost(self.path_cost, self.state,
135.                                       action, next_state))
136.
137.     def solution(self):
138.         """Return the sequence of actions to go from the root to this node.
139.
140.        :return: sequence of actions
141.        :rtype: list
142.        """
143.         return [node.action for node in self.path()[1:]]
144.
145.     def solve(self):
146.         """Return the sequence of states to go from the root to this node.
147.
148.        :return: list of states
149.        :rtype: list
150.        """
151.         return [node.state for node in self.path()[0:]]
152.
153.     def path(self):
154.         """Return a list of nodes forming the path from the root to this node.
155.
156.        :return: list of states from the path
157.        :rtype: list(Node)
158.        """
159.         x, result = self, []
160.         while x:
161.             result.append(x)
162.             x = x.parent
163.         result.reverse()
164.         return result
165.
166.     """We want the queue of nodes at breadth_first_search or
167.    astar_search to not contain states-duplicates, so the nodes that
168.    contain the same condition we treat as the same. [Problem: this can
169.    not be desirable in other situations.]"""
170.
171.     def __eq__(self, other):
172.         return isinstance(other, Node) and self.state == other.state
173.
174.     def __hash__(self):
175.         return hash(self.state)
176.
177.
178. """
179. Definitions of helper structures for storing the list of generated, but not checked nodes
180. """
181.
182.
183. class Queue:
184.     """Queue is an abstract class/interface. There are three types:
185.        Stack(): Last In First Out Queue (stack).
186.        FIFOQueue(): First In First Out Queue.
187.        PriorityQueue(order, f): QQueue in sorted order (default min-first).
188.    """
189.
190.     def __init__(self):
191.         raise NotImplementedError
192.
193.     def append(self, item):
194.         """Adds the item into the queue
195.
196.        :param item: given element
197.        :return: None
198.        """
199.         raise NotImplementedError
200.
201.     def extend(self, items):
202.         """Adds the items into the queue
203.
204.        :param items: given elements
205.        :return: None
206.        """
207.         raise NotImplementedError
208.
209.     def pop(self):
210.         """Returns the first element of the queue
211.
212.        :return: first element
213.        """
214.         raise NotImplementedError
215.
216.     def __len__(self):
217.         """Returns the number of elements in the queue
218.
219.        :return: number of elements in the queue
220.        :rtype: int
221.        """
222.         raise NotImplementedError
223.
224.     def __contains__(self, item):
225.         """Check if the queue contains the element item
226.
227.        :param item: given element
228.        :return: whether the queue contains the item
229.        :rtype: bool
230.        """
231.         raise NotImplementedError
232.
233.
234. class Stack(Queue):
235.     """Last-In-First-Out Queue."""
236.
237.     def __init__(self):
238.         self.data = []
239.
240.     def append(self, item):
241.         self.data.append(item)
242.
243.     def extend(self, items):
244.         self.data.extend(items)
245.
246.     def pop(self):
247.         return self.data.pop()
248.
249.     def __len__(self):
250.         return len(self.data)
251.
252.     def __contains__(self, item):
253.         return item in self.data
254.
255.
256. class FIFOQueue(Queue):
257.     """First-In-First-Out Queue."""
258.
259.     def __init__(self):
260.         self.data = []
261.
262.     def append(self, item):
263.         self.data.append(item)
264.
265.     def extend(self, items):
266.         self.data.extend(items)
267.
268.     def pop(self):
269.         return self.data.pop(0)
270.
271.     def __len__(self):
272.         return len(self.data)
273.
274.     def __contains__(self, item):
275.         return item in self.data
276.
277.
278. class PriorityQueue(Queue):
279.     """A queue in which the minimum (or maximum) element is returned first
280.     (as determined by f and order). This structure is used in
281.     informed search"""
282.
283.     def __init__(self, order=min, f=lambda x: x):
284.         """
285.        :param order: sorting function, if order is min, returns the element
286.                      with minimal f (x); if the order is max, then returns the
287.                      element with maximum f (x).
288.        :param f: function f(x)
289.        """
290.         assert order in [min, max]
291.         self.data = []
292.         self.order = order
293.         self.f = f
294.
295.     def append(self, item):
296.         bisect.insort_right(self.data, (self.f(item), item))
297.
298.     def extend(self, items):
299.         for item in items:
300.             bisect.insort_right(self.data, (self.f(item), item))
301.
302.     def pop(self):
303.         if self.order == min:
304.             return self.data.pop(0)[1]
305.         return self.data.pop()[1]
306.
307.     def __len__(self):
308.         return len(self.data)
309.
310.     def __contains__(self, item):
311.         return any(item == pair[1] for pair in self.data)
312.
313.     def __getitem__(self, key):
314.         for _, item in self.data:
315.             if item == key:
316.                 return item
317.
318.     def __delitem__(self, key):
319.         for i, (value, item) in enumerate(self.data):
320.             if item == key:
321.                 self.data.pop(i)
322.
323.
324. # coding=utf-8
325. import sys
326.
327. """
328. Uninformed tree search.
329. Within the tree we do not solve the loops.
330. """
331.
332.
333. def tree_search(problem, fringe):
334.     """Search through the successors of a problem to find a goal.
335.
336.    :param problem: given problem
337.    :param fringe:  empty queue
338.    :return: Node
339.    """
340.     fringe.append(Node(problem.initial))
341.     while fringe:
342.         node = fringe.pop()
343.         print(node.state)
344.         if problem.goal_test(node.state):
345.             return node
346.         fringe.extend(node.expand(problem))
347.     return None
348.
349.
351.     """Search the shallowest nodes in the search tree first.
352.
353.    :param problem: given problem
354.    :return: Node
355.    """
356.     return tree_search(problem, FIFOQueue())
357.
358.
359. def depth_first_tree_search(problem):
360.     """Search the deepest nodes in the search tree first.
361.
362.    :param problem: given problem
363.    :return: Node
364.    """
365.     return tree_search(problem, Stack())
366.
367.
368. """
369. Uninformed graph search
370. The main difference is that here we do not allow loops,
371. i.e. repetition of states
372. """
373.
374.
375. def graph_search(problem, fringe):
376.     """Search through the successors of a problem to find a goal.
377.     If two paths reach a state, only use the best one.
378.
379.    :param problem: given problem
380.    :param fringe: empty queue
381.    :return: Node
382.    """
383.     closed = set()
384.     fringe.append(Node(problem.initial))
385.     while fringe:
386.         node = fringe.pop()
387.         if problem.goal_test(node.state):
388.             return node
389.         if node.state not in closed:
391.             fringe.extend(node.expand(problem))
392.     return None
393.
394.
396.     """Search the shallowest nodes in the search tree first.
397.
398.    :param problem: given problem
399.    :return: Node
400.    """
401.     return graph_search(problem, FIFOQueue())
402.
403.
404. def depth_first_graph_search(problem):
405.     """Search the deepest nodes in the search tree first.
406.
407.    :param problem: given problem
408.    :return: Node
409.    """
410.     return graph_search(problem, Stack())
411.
412.
413. def depth_limited_search(problem, limit=50):
414.     def recursive_dls(node, problem, limit):
415.         """Helper function for depth limited"""
416.         cutoff_occurred = False
417.         if problem.goal_test(node.state):
418.             return node
419.         elif node.depth == limit:
420.             return 'cutoff'
421.         else:
422.             for successor in node.expand(problem):
423.                 result = recursive_dls(successor, problem, limit)
424.                 if result == 'cutoff':
425.                     cutoff_occurred = True
426.                 elif result is not None:
427.                     return result
428.         if cutoff_occurred:
429.             return 'cutoff'
430.         return None
431.
432.     return recursive_dls(Node(problem.initial), problem, limit)
433.
434.
435. def iterative_deepening_search(problem):
436.     for depth in range(sys.maxsize):
437.         result = depth_limited_search(problem, depth)
438.         if result is not 'cutoff':
439.             return result
440.
441.
442. def uniform_cost_search(problem):
443.     """Search the nodes in the search tree with lowest cost first."""
444.     return graph_search(problem, PriorityQueue(lambda a, b:
445.                                                a.path_cost < b.path_cost))
446.
447.
448. from enum import Enum
449.
450.
451. # write class definitions after this comment line
452. class Actions(Enum):
453.     RIGHT = 1
454.     LEFT = 2
455.     UP = 3
456.     DOWN = 4
457.
458.
459. class ObstacleProblem(Problem):
460.
461.     def __init__(self, initial, goal):
462.         super().__init__(initial, goal)
463.         self.initial = initial
464.         self.goal = goal
465.
466.     def goal_test(self, state):
467.         g = self.goal
468.         (x, y) = state[0]
469.         return x == g[0] and y == g[1]
470.
471.     def successor(self, state):
472.         successors = dict()
473.
474.         move(Actions.RIGHT, state, successors)
475.         move(Actions.LEFT, state, successors)
476.         move(Actions.UP, state, successors)
477.         move(Actions.DOWN, state, successors)
478.
479.         return successors
480.
481.     def actions(self, state):
482.         return self.successor(state).keys()
483.
484.     def result(self, state, action):
485.         possible = self.successor(state)
486.         return possible[action]
487.
488.     def value(self):
489.         pass
490.
491.
492. def move(action, state, successors):
493.     x, y = state[0]
494.     o1 = state[1]
495.     o2 = state[2]
496.     o3 = state[3]
497.     o1_new = update_obstacle1(o1)
498.     o2_new = update_obstacle2(o2)
499.     o3_new = update_obstacle3(o3)
500.
501.     if action == Actions.RIGHT:
502.         y = y + 1
503.         action_done = "Desno"
504.     elif action == Actions.LEFT:
505.         y = y - 1
506.         action_done = "Levo"
507.     elif action == Actions.UP:
508.         x = x - 1
509.         action_done = "Gore"
510.     elif action == Actions.DOWN:
511.         x = x + 1
512.         action_done = "Dolu"
513.     else:
514.         action_done = "Invalid"
515.
516.     if is_valid(x, y, o1_new, o2_new, o3_new):
517.         new_man_pos = (x, y)
518.         new_state = (new_man_pos, o1_new, o2_new, o3_new)
519.         successors[action_done] = new_state
520.
521.
522. def update_obstacle1(obstacle):
523.     x = obstacle[0]
524.     y = obstacle[1]
525.     direction = obstacle[2]
526.
527.     if (y == 0 and direction == -1) or (y == 4 and direction == 1):
528.         direction *= -1
529.
530.     y_new = y + direction
531.     new_pos = (x, y_new, direction)
532.     return new_pos
533.
534.
535. def update_obstacle2(obstacle):
536.     x = obstacle[0]
537.     y = obstacle[1]
538.     direction = obstacle[2]
539.
540.     if (x == 5 and direction == 1) or (x == 9 and direction == -1):
541.         direction *= -1
542.
543.     x_new = x - direction
544.     y_new = y + direction
545.     new_pos = x_new, y_new, direction
546.     return new_pos
547.
548.
549. def update_obstacle3(obstacle):
550.     x = obstacle[0]
551.     y = obstacle[1]
552.     direction = obstacle[2]
553.
554.     if (x == 5 and direction == 1) or (x == 9 and direction == -1):
555.         direction *= -1
556.     x_new = x - direction
557.     new_pos = x_new, y, direction
558.     return new_pos
559.
560.
561. def is_valid(x, y, o1, o2, o3):
562.     # Map check
563.     if x < 0 or y < 0 or x > 10 or y > 10:
564.         return False
565.     if y > 5 and x < 5:
566.         return False
567.
568.     # Obstacle collision check
569.     if (x == o1[0] and y == o1[1]) or (x == o1[0] and (y == o1[1] + 1)):
570.         return False
571.
572.     if (x == o2[0] and y == o2[1]) or (x == o2[0] + 1 and y == o2[1]) \
573.             or (x == o2[0] and y == o2[1] + 1) or (x == o2[0] + 1 and y == o2[1] + 1):
574.         return False
575.
576.     if (x == o3[0] and y == o3[1]) or (x == o3[0] + 1 and y == o3[1]):
577.         return False
578.
579.     return True
580.
581.
582. if __name__ == '__main__':
583.     man_row = int(input())
584.     man_column = int(input())
585.     house_row = int(input())
586.     house_column = int(input())
587.     # continue the code for solving the problem after this comment line
588.
589.     goal_state = (house_row, house_column)
590.
591.     man = (man_row, man_column)
592.     obstacle1 = (2, 2, -1)  # left
593.     obstacle2 = (7, 2, 1)  # upward-right
594.     obstacle3 = (7, 8, -1)  # downward
595.     initial_state = (man, obstacle1, obstacle2, obstacle3)
596.     solution_space = ObstacleProblem(initial_state, goal_state)
597.