이번에는 A*(A-star)알고리즘이라는 것을 배워볼 것이다. 너무나도 중요한 알고리즘이다. 고맙게도 이해하기 쉽기도 하다. 쓰기는 힘들다 ㅠ 그 이유도 이제부터 알아본다.
왼쪽과 같은 지도가 있었다면, 기존의 Expand를 하는 방식으로는 오른쪽의 탁 트인 공간을 모두 살피느라 시간이 오래 걸렸을 것이다. 우리들은 지도를 본다면, 아래에 붙어서 곧장 가기만 하면 목표지점에 바로 도달할 수 있는 것을 알고 있는데, 이렇게 작동하는 알고리즘을 설계할 수는 없을까? 하는 발상에서 시작된 알고리즘이 바로 이 A*알고리즘이다.
이를 위해서는 기존의 지도와 더불어 크기가 같은 또 하나의 지도가 필요하다. 위에서는 이를 목표지점까지 도달하기 위한 Cost로 보이고 있으며, 위에 HEURISTIC FUNCTION이라고 친절하게 적혀 있다. 이것이 바로 A*알고리즘의 핵심이다.
지금까지의 Expand 알고리즘에서는 Cost를 단순히 움직인 칸수로 해주었지만, A*에서는 다르다!!
기존의 Cost를 g-value라고 했다면, Heuristic Function에서 해당하는 칸의 값을 더해 이를 f-value라고 할 것이다. 그리고 g-value가 아닌 f-value를 최소화하는 경우에 한해서만 탐색을 계속할 것이다. 위 예를 보자. 4, 2 칸에서 컴퓨터는 위로 갈지, 아래로 갈지 선택의 기로에 놓인다. 두 경우 모두 g-value는 같기 때문이다. 하지만!! Heuristic Function을 도입해 보자.
위로 움직일 때
- 좌표 3, 2
- g-value 7
- f-value 4
우측으로 움직일 때
- 좌표 4, 3
- g-value 7
- f-value 2
이렇게 되어 value들의 합산이 더 적은 4, 3으로 움직이게 되는 것이다!!
이렇게 해서 갈 필요가 없는 윗부분을 지나칠 수 있어 엄청난 효율을 갖게 되었다. 여기에서 의문이 생길 수가 있는데, 그럼 이 Heuristic Function은 어떻게 만들어 주어야 하는 것일까?? 파란 글씨에 그 해답이 적혀 있다. Heuristic Function의 값들은 목표 지점까지의 거리보다 같거나 작아야 한다. 즉, Heuristic Function은 여러개가 존재할 수 있다는 것이다.
간단히 예를 들어서 위와 같이 만들 수도 있는 것이다. 목적지까지의 거리보다 작기만 상황에 따라 작아도 괜찮다. 이렇게 만들어진 Heuristic Function이 사용할 수 있으면 "Admissible"하다고 한다.
그럼 아래와 같이 실제로 이를 구현해 보는 것이 과제이다.
기존의 방식은 이렇게 윗부분도 건드렸지만
우리의 갓갓 A*님은 그런거 따위 모르신다 이 말씀!!! 그럼 문제를 풀어보자. 그다지 어렵지 않다. 제공되는 것은 이전 과제의 코드이다. 이를 수정해서 A* Version을 만들어야 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | # ----------- # User Instructions: # # Modify the the search function so that it becomes # an A* search algorithm as defined in the previous # lectures. # # Your function should return the expanded grid # which shows, for each element, the count when # it was expanded or -1 if the element was never expanded. # # If there is no path from init to goal, # the function should return the string 'fail' # ---------- grid = [[0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0]] heuristic = [[9, 8, 7, 6, 5, 4], [8, 7, 6, 5, 4, 3], [7, 6, 5, 4, 3, 2], [6, 5, 4, 3, 2, 1], [5, 4, 3, 2, 1, 0]] init = [0, 0] goal = [len(grid)-1, len(grid[0])-1] cost = 1 delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right delta_name = ['^', '<', 'v', '>'] def search(grid,init,goal,cost,heuristic): # ---------------------------------------- # modify the code below # ---------------------------------------- closed = [[0 for col in range(len(grid[0]))] for row in range(len(grid))] closed[init[0]][init[1]] = 1 expand = [[-1 for col in range(len(grid[0]))] for row in range(len(grid))] action = [[-1 for col in range(len(grid[0]))] for row in range(len(grid))] x = init[0] y = init[1] g = 0 open = [[g, x, y]] found = False # flag that is set when search is complete resign = False # flag set if we can't find expand count = 0 while not found and not resign: if len(open) == 0: resign = True return "Fail" else: open.sort() open.reverse() next = open.pop() x = next[1] y = next[2] g = next[0] expand[x][y] = count count += 1 if x == goal[0] and y == goal[1]: found = True else: for i in range(len(delta)): x2 = x + delta[i][0] y2 = y + delta[i][1] if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 < len(grid[0]): if closed[x2][y2] == 0 and grid[x2][y2] == 0: g2 = g + cost open.append([g2, x2, y2]) closed[x2][y2] = 1 return expand | cs |
정답은 아래에 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | # ----------- # User Instructions: # # Modify the the search function so that it becomes # an A* search algorithm as defined in the previous # lectures. # # Your function should return the expanded grid # which shows, for each element, the count when # it was expanded or -1 if the element was never expanded. # # If there is no path from init to goal, # the function should return the string 'fail' # ---------- grid = [[0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0]] heuristic = [[9, 8, 7, 6, 5, 4], [8, 7, 6, 5, 4, 3], [7, 6, 5, 4, 3, 2], [6, 5, 4, 3, 2, 1], [5, 4, 3, 2, 1, 0]] init = [0, 0] goal = [len(grid)-1, len(grid[0])-1] cost = 1 delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right delta_name = ['^', '<', 'v', '>'] def search(grid,init,goal,cost, heuristic): # ---------------------------------------- # modify the code below # ---------------------------------------- closed = [[0 for col in range(len(grid[0]))] for row in range(len(grid))] closed[init[0]][init[1]] = 1 expand = [[-1 for col in range(len(grid[0]))] for row in range(len(grid))] action = [[-1 for col in range(len(grid[0]))] for row in range(len(grid))] x = init[0] y = init[1] g = 0 f = 0 open = [[f, g, x, y]] found = False # flag that is set when search is complete resign = False # flag set if we can't find expand count = 0 while not found and not resign: if len(open) == 0: resign = True return "Fail" else: open.sort() open.reverse() next = open.pop() x = next[2] y = next[3] g = next[1] f = next[0] expand[x][y] = count count += 1 if x == goal[0] and y == goal[1]: found = True else: for i in range(len(delta)): x2 = x + delta[i][0] y2 = y + delta[i][1] if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 < len(grid[0]): if closed[x2][y2] == 0 and grid[x2][y2] == 0: g2 = g + cost f2 = g2 + heuristic[x2][y2] open.append([f2, g2, x2, y2]) closed[x2][y2] = 1 #for i in range(len(expand)): # print(expand[i]) return expand ##### Do Not Modify ###### #import grader print('search',search(grid,init,goal,cost, heuristic)) #try: # response = grader.run_grader(search) # print('response', response) #except Exception as err: # print(str(err)) #) #except Exception as err: # print(str(err)) | cs |
A* 알고리즘이 자율주행 자동차에서 실제로 어떻게 쓰였는지 보이는 영상이다. 참고로, 이 강좌를 진행하는 Sebastian Thrun교수는 Darpa Challenge에서 Stenly로 우승을 했던 장본인이다.
====================================================================
다음으로 배워 볼 내용은 Dynamic Programming이라는 것이다. 사실 Dynamic Programming이라 함은 복잡한 문제를 잘게 나누어서 푼다는 의미를 가지고 있다고 한다. 일반적으로 우리가 Programming이라고 할 때 코드로 뚝딱뚝딱 하는 그런 것이 아니고, 전혀 Dynamic 하지도 않아서 기억하며 풀기라고 하시는 분도 있다고 한다.
어쨌든, 앞서 최선의 경로를 찾는 이 문제에 Dynamic Programming의 개념을 도입해 보자,
우리가 필요한 것은 전체 지도와, 목표 지점일 뿐이다. 왜냐? 지도상의 모든 지점에서 목표까지의 최적의 경로를 찾을 것이기 때문이다.
이렇게 말이다~ 그리고 이렇게 각 위치에서 해당되는 움직임 Mapping 해주는 위 지도를 Policy라고 할 것이다. 이 Policy를 설계하는 것이 우리의 목표이다. 바로 실습으로 들어가기 전에, 간단한 힌트를 주고 있다.
빨간 박스가 목표 지점이라고 하였을 때, 각 지점에서 빨간 박스까지 걸리는 거리를 value라고 하자. 그럼 이 value를 구하는 Function을 오른쪽과 같이 설정할 수 있을 것이다.
인접 위치들 중에서 가장 작은 값을 가진 곳의 value + 1
그리고 목표 지점은 value가 0이다. 그래서 value map은 목표 지점에서부터 가까운 순으로 1씩 더해가면서 위와 같이 만들어질 것이다. 완벽한 policy를 만들기에 앞서 이 value를 계산하는 과정부터 해보자.
이런 gird가 주어져 있고 장애물은 99의 값을 가지도록 되어 있다. 이 상황에서 아래와 같이 모든 지점에서의 value를 나타내는 지도를 만드는 것이 과제이다. 그럼 아래에 문제를 첨부한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | # ---------- # User Instructions: # # Create a function compute_value which returns # a grid of values. The value of a cell is the minimum # number of moves required to get from the cell to the goal. # # If a cell is a wall or it is impossible to reach the goal from a cell, # assign that cell a value of 99. # ---------- grid = [[0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0]] goal = [len(grid)-1, len(grid[0])-1] cost = 1 # the cost associated with moving from a cell to an adjacent one delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right delta_name = ['^', '<', 'v', '>'] def compute_value(grid,goal,cost): # ---------------------------------------- # insert code below # ---------------------------------------- # make sure your function returns a grid of values as # demonstrated in the previous video. return value | cs |
다시 말하지만, 목표 지점에서부터 거꾸로 계산하는 것이다!! 정답은 아래에 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | # ---------- # User Instructions: # # Create a function compute_value which returns # a grid of values. The value of a cell is the minimum # number of moves required to get from the cell to the goal. # # If a cell is a wall or it is impossible to reach the goal from a cell, # assign that cell a value of 99. # ---------- grid = [[0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0]] goal = [len(grid)-1, len(grid[0])-1] cost = 1 # the cost associated with moving from a cell to an adjacent one delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right delta_name = ['^', '<', 'v', '>'] def compute_value(grid,goal,cost): value = [[99 for row in range(len(grid[0]))] for col in range(len(grid))] change = True while change: change = False for x in range(len(grid)): for y in range(len(grid[0])): if goal[0] == x and goal[1] == y: if value[x][y] > 0: value[x][y] = 0 change = True elif grid[x][y] == 0: for a in range(len(delta)): x2 = x + delta[a][0] y2 = y + delta[a][1] if x2 >=0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]) and grid[x2][y2] == 0: v2 = value[x2][y2] + cost if v2 < value[x][y]: change = True value[x][y] = v2 for i in range(len(value)): print(value[i]) # make sure your function returns a grid of values as # demonstrated in the previous video. return value | cs |
참고로 이에는 다양한 답이 나올 수 있다.
value = [[99 for row in range(len(grid[0]))] for col in range(len(grid))]
처음에 모든 지점이 장애물의 값(위 사진을 다시 보면 장애물이 있는 지점은 99의 값을 가지게 한다고 되어 있음)과 같은 99를 가지게 한다.
1 2 3 4 | if goal[0] == x and goal[1] == y: if value[x][y] > 0: value[x][y] = 0 change = True | cs |
그리고 목표 지점은 0의 값을 가지게 한다. 여기서부터 반복의 시작이다.
1 2 3 4 5 6 7 8 | delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right for a in range(len(delta)): x2 = x + delta[a][0] y2 = y + delta[a][1] | cs |
상 하 좌 우로 움직이는 각각의 행동들에 대해서 탐색을 시행하고,
1 2 3 4 5 | if x2 >=0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]) and grid[x2][y2] == 0: v2 = value[x2][y2] + cost if v2 < value[x][y]: change = True value[x][y] = v2 | cs |
그 지점이 벽이 아니고 존재한다, 그리고 자신보다 작은 value를 가지고 있다, 하면 그 value + 1(자신과 1만큼 인접해 있으므로)을 자신의 value로 설정한다. 무슨 말인지 나도 이해가 가지 않아 투박한 그림으로 나타낸다.
이런 식을 반복하게 된다!
그럼 최종적으로 위와 같은 최적의(optimum) policy를 찾는 실습을 해 보자!! 이전 value를 찾는 과제의 답을 수정하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | grid = [[0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0]] init = [0, 0] goal = [len(grid)-1, len(grid[0])-1] cost = 1 # the cost associated with moving from a cell to an adjacent one delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right delta_name = ['^', '<', 'v', '>'] def optimum_policy(grid,goal,cost): # ---------------------------------------- # modify code below # ---------------------------------------- value = [[99 for row in range(len(grid[0]))] for col in range(len(grid))] change = True while change: change = False for x in range(len(grid)): for y in range(len(grid[0])): if goal[0] == x and goal[1] == y: if value[x][y] > 0: value[x][y] = 0 change = True elif grid[x][y] == 0: for a in range(len(delta)): x2 = x + delta[a][0] y2 = y + delta[a][1] if x2 >= 0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]) and grid[x2][y2] == 0: v2 = value[x2][y2] + cost if v2 < value[x][y]: change = True value[x][y] = v2 return policy | cs |
정답 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | # ---------- # User Instructions: # # Write a function optimum_policy that returns # a grid which shows the optimum policy for robot # motion. This means there should be an optimum # direction associated with each navigable cell from # which the goal can be reached. # # Unnavigable cells as well as cells from which # the goal cannot be reached should have a string # containing a single space (' '), as shown in the # previous video. The goal cell should have '*'. # ---------- grid = [[0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0]] init = [0, 0] goal = [len(grid)-1, len(grid[0])-1] cost = 1 # the cost associated with moving from a cell to an adjacent one delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right delta_name = ['^', '<', 'v', '>'] def optimum_policy(grid,goal,cost): value = [[99 for row in range(len(grid[0]))] for col in range(len(grid))] policy = [[' ' for row in range(len(grid[0]))] for col in range(len(grid))] change = True while change: change = False for x in range(len(grid)): for y in range(len(grid[0])): if goal[0] == x and goal[1] == y: if value[x][y] > 0: value[x][y] = 0 policy[x][y] = '*' change = True elif grid[x][y] == 0: for a in range(len(delta)): x2 = x + delta[a][0] y2 = y + delta[a][1] if x2 >=0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]) and grid[x2][y2] == 0: v2 = value[x2][y2] + cost if v2 < value[x][y]: change = True value[x][y] = v2 policy[x][y] = delta_name[a] for i in range(len(policy)): print(policy[i]) # make sure your function returns a grid of values as # demonstrated in the previous video. return policy | cs |
참고로 수정된 부분은 이 세 줄 밖에 없다.
1 2 3 4 5 | policy = [[' ' for row in range(len(grid[0]))] for col in range(len(grid))] policy[x][y] = '*' policy[x][y] = delta_name[a] | cs |
모든 칸이 비어 있는 지도를 만들고 목표 지점에는 *을 그렸다. 그리고 마지막 문장은 for문 안에서 돌고 있는데, 어떠한 움직임이 시행되었는지를 기록하게 된다!!
=========================================================================
이번에는 뭔가 끝판왕 같은 policy를 구현해 보자.
실제로 자동차가 움직인다고 생각하면, 이렇게 방향도 고려해야 할 것이다. 후진은 하진 않을 것이고, 좌회전, 전진, 우회전의 움직임을 취할 수 있을 것이다. 그리고 그냥 화살표로 나타내는 것이 아니라 아래와 같이 어떤 움직임을 하였는지도 보이려고 한다.
여기에서 ACTION이라는 리스트가 추가가 되었는데, 앞서 말하였던, 우회전, 전진, 좌회전 움직임을 나타내기 위해서이다. 그럼 그리고, 각 움직임마다. 그 COST가 다르다고 해주자. 앞서 좌회전을 하기 위해서는 차선도 바꾸고 신호도 기다린다고 하였는데, 이를 고려해서 좌회전에 대한 COST를 20으로 높여버리면
우리의 꼬마 자동차는 돌아돌아 목적지로 가게 된다. 이를 구현해 보는 것이 과제이다. 상당히 TRICKY하다. 아래 코드를 사용해서 해야 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | # ---------- # User Instructions: # # Implement the function optimum_policy2D below. # # You are given a car in grid with initial state # init. Your task is to compute and return the car's # optimal path to the position specified in goal; # the costs for each motion are as defined in cost. # # There are four motion directions: up, left, down, and right. # Increasing the index in this array corresponds to making a # a left turn, and decreasing the index corresponds to making a # right turn. forward = [[-1, 0], # go up [ 0, -1], # go left [ 1, 0], # go down [ 0, 1]] # go right forward_name = ['up', 'left', 'down', 'right'] # action has 3 values: right turn, no turn, left turn action = [-1, 0, 1] action_name = ['R', '#', 'L'] # EXAMPLE INPUTS: # grid format: # 0 = navigable space # 1 = unnavigable space grid = [[1, 1, 1, 0, 0, 0], [1, 1, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0], [1, 1, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1]] init = [4, 3, 0] # given in the form [row,col,direction] # direction = 0: up # 1: left # 2: down # 3: right goal = [2, 0] # given in the form [row,col] cost = [2, 1, 20] # cost has 3 values, corresponding to making # a right turn, no turn, and a left turn # EXAMPLE OUTPUT: # calling optimum_policy2D with the given parameters should return # [[' ', ' ', ' ', 'R', '#', 'R'], # [' ', ' ', ' ', '#', ' ', '#'], # ['*', '#', '#', '#', '#', 'R'], # [' ', ' ', ' ', '#', ' ', ' '], # [' ', ' ', ' ', '#', ' ', ' ']] # ---------- # ---------------------------------------- # modify code below # ---------------------------------------- def optimum_policy2D(grid,init,goal,cost): return policy2D | cs |
정답은 아래와 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | # ---------- # User Instructions: # # Implement the function optimum_policy2D below. # # You are given a car in grid with initial state # init. Your task is to compute and return the car's # optimal path to the position specified in goal; # the costs for each motion are as defined in cost. # # There are four motion directions: up, left, down, and right. # Increasing the index in this array corresponds to making a # a left turn, and decreasing the index corresponds to making a # right turn. forward = [[-1, 0], # go up [ 0, -1], # go left [ 1, 0], # go down [ 0, 1]] # go right forward_name = ['up', 'left', 'down', 'right'] # action has 3 values: right turn, no turn, left turn action = [-1, 0, 1] action_name = ['R', '#', 'L'] # EXAMPLE INPUTS: # grid format: # 0 = navigable space # 1 = unnavigable space grid = [[1, 1, 1, 0, 0, 0], [1, 1, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0], [1, 1, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1]] init = [4, 3, 0] # given in the form [row,col,direction] # direction = 0: up # 1: left # 2: down # 3: right goal = [2, 0] # given in the form [row,col] cost = [2, 1, 20] # cost has 3 values, corresponding to making # a right turn, no turn, and a left turn # EXAMPLE OUTPUT: # calling optimum_policy2D with the given parameters should return # [[' ', ' ', ' ', 'R', '#', 'R'], # [' ', ' ', ' ', '#', ' ', '#'], # ['*', '#', '#', '#', '#', 'R'], # [' ', ' ', ' ', '#', ' ', ' '], # [' ', ' ', ' ', '#', ' ', ' ']] # ---------- # ---------------------------------------- # modify code below # ---------------------------------------- def optimum_policy2D(grid,init,goal,cost): value = [[[999 for facing in range(len(forward))]\ for col in range(len(grid[0]))]\ for row in range(len(grid))] policy = [[[' ' for facing in range(len(forward))]\ for col in range(len(grid[0]))]\ for row in range(len(grid))] policy2D = [[' ' for x in range(len(grid[0]))] for y in range(len(grid))] change = True while change: change = False for x in range(len(grid)): for y in range(len(grid[0])): for f in range(len(forward)): if x == goal[0] and y == goal[1]: if value[x][y][f] > 0: value[x][y][f] = 0 policy[x][y][f] = '*' change = True elif grid[x][y] == 0: for f2 in range(len(forward)): x2 = x + forward[f2][0] y2 = y + forward[f2][1] if x2 >= 0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]) and grid[x2][y2] == 0: temp = value[x2][y2][f2] for a in range(len(action)): if (f + action[a]) % len(forward) == f2: v2 = temp + cost[a] if v2 < value[x][y][f]: value[x][y][f] = v2 policy[x][y][f] = action_name[a] change = True x = init[0] y = init[1] f = init[2] policy2D[x][y] = policy[x][y][f] while policy[x][y][f] != '*': if policy[x][y][f] == 'R': f = (f - 1) % 4 elif policy[x][y][f] == 'L': f = (f + 1) % 4 x += forward[f][0] y += forward[f][1] policy2D[x][y] = policy[x][y][f] return policy2D for line in optimum_policy2D(grid,init,goal,cost): print(line) | cs |
몇 가지 TRICK이 쓰인 것이 보일텐데 우선 첫번째로,
1 | if (f + action[a]) % len(forward) == f2: | cs |
요 부분이다. f는 지금 로봇이 가리키고 있는 방향이고, action은 우회전, 직진, 좌회전의 움직임, f2는 움직임 뒤에 어떤 방향을 가리키고 있는지를 의미한다. 왜 이렇게 하였냐 하면
그림판으로 만드려다 도저히 너무 이상해서 직접 그려서 해 보았다. 이해가 되려나 모르겠다. 예를 들어 위를 바라보고 있었던 경우 원래 방향은 0이고, 우회전을 하면 3, 직진하면 0, 좌회전을 하면 1이 된다. 단순히 f + 해당 action을 하면 된다고 생각할 수도 있지만 원래 바라보고 있던 방향이 오른쪽 (3) 이었다면 좌회전을 했을 때, 4가 되어 버리므로 이에 대한 처리가 필료하다 그래서 정답에서는 mod 4를 취해 주었던 것이다.
1 2 3 4 5 6 7 8 | while policy[x][y][f] != '*': if policy[x][y][f] == 'R': f = (f - 1) % 4 elif policy[x][y][f] == 'L': f = (f + 1) % 4 x += forward[f][0] y += forward[f][1] policy2D[x][y] = policy[x][y][f] | cs |
Policy에 대한 것 또한 마찬가지이다. 최적의 경로만 나타내기 위해서는 목표 지점에서부터 거꾸로 가야 했음을 기억하고 있을 것이다. 여기에서도 마찬가지이다. 다만 방향성을 고려해주어야 하기 때문에, 우회전에서는 (방향 - 1) mod 4
를 해주고 좌회전에서는 (방향 + 1) mod 4를 취해준 것이 보인다. 사실 나는 무수한 if - else문으로 처리하려고 했었다. 그래도 문제될 것은 없지만 이 방법이 훨씬 보기는 편한 것 같다.
마지막 cost를 바꿔가면서 결과를 확인해보길 바란다.
===========================================================================
그럼 다음 문제, 휴 문제가 너무나 많다. 포스트를 쓰는 데에도 몇시간이 걸리는지 모르겠다.
실제로 최단, 최적의 경로를 짰다고 해서 이것이 다가 아니다. 위 그림을 보자. 벽이 있는데, 최단거리로 가기 위해서 아슬아슬하게 지나가라고 경로를 짜 주는것 보다, 움직임의 오류를 생각해서 벽과 거리를 조금 두게 하는 것이 더 현명할 것이다. 이런 모델을 사용해 볼 것이고, Stochastic Motion이라고 부른다.
옆에 벽도 있고, 로봇은 우리가 시킨 대로만 움직이지 않고, 실패할 확률도 가지고 있다. 이런 확률들과 weight를 모두 고려해서 앞으로 전진할 때의 cost를 정해주려고 한다. 아래에 예시들이 나와 있는데, 이들을 보면 감이 올 것이다.
이러한 모델을 만들어 보는 것이 과제!! 문제는 아래와 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | # -------------- # USER INSTRUCTIONS # # Write a function called stochastic_value that # returns two grids. The first grid, value, should # contain the computed value of each cell as shown # in the video. The second grid, policy, should # contain the optimum policy for each cell. # # -------------- # GRADING NOTES # # We will be calling your stochastic_value function # with several different grids and different values # of success_prob, collision_cost, and cost_step. # In order to be marked correct, your function must # RETURN (it does not have to print) two grids, # value and policy. # # When grading your value grid, we will compare the # value of each cell with the true value according # to this model. If your answer for each cell # is sufficiently close to the correct answer # (within 0.001), you will be marked as correct. delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right delta_name = ['^', '<', 'v', '>'] # Use these when creating your policy grid. # --------------------------------------------- # Modify the function stochastic_value below # --------------------------------------------- def stochastic_value(grid,goal,cost_step,collision_cost,success_prob): failure_prob = (1.0 - success_prob)/2.0 # Probability(stepping left) = prob(stepping right) = failure_prob value = [[collision_cost for col in range(len(grid[0]))] for row in range(len(grid))] policy = [[' ' for col in range(len(grid[0]))] for row in range(len(grid))] return value, policy # --------------------------------------------- # Use the code below to test your solution # --------------------------------------------- grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 1, 0]] goal = [0, len(grid[0])-1] # Goal is in top right corner cost_step = 1 collision_cost = 1000 success_prob = 0.5 value,policy = stochastic_value(grid,goal,cost_step,collision_cost,success_prob) for row in value: print row for row in policy: print row # Expected outputs: # #[471.9397246855924, 274.85364957758316, 161.5599867065471, 0], #[334.05159958720344, 230.9574434590965, 183.69314862430264, 176.69517762501977], #[398.3517867450282, 277.5898270101976, 246.09263437756917, 335.3944132514738], #[700.1758933725141, 1000, 1000, 668.697206625737] # # ['>', 'v', 'v', '*'] # ['>', '>', '^', '<'] # ['>', '^', '^', '<'] # ['^', ' ', ' ', '^'] | cs |
움직이려는 칸과 좌, 우 칸을 고려해서 짜야 한다. 참고로 성공할 확률이 50%라 하면, 오른쪽으로 잘못 움직일 확률과 왼쪽으로 잘못 움직일 확률은 똑같이 25%가 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | # -------------- # USER INSTRUCTIONS # # Write a function called stochastic_value that # returns two grids. The first grid, value, should # contain the computed value of each cell as shown # in the video. The second grid, policy, should # contain the optimum policy for each cell. # # -------------- # GRADING NOTES # # We will be calling your stochastic_value function # with several different grids and different values # of success_prob, collision_cost, and cost_step. # In order to be marked correct, your function must # RETURN (it does not have to print) two grids, # value and policy. # # When grading your value grid, we will compare the # value of each cell with the true value according # to this model. If your answer for each cell # is sufficiently close to the correct answer # (within 0.001), you will be marked as correct. delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right delta_name = ['^', '<', 'v', '>'] # Use these when creating your policy grid. # --------------------------------------------- # Modify the function stochastic_value below # --------------------------------------------- def stochastic_value(grid,goal,cost_step,collision_cost,success_prob): failure_prob = (1.0 - success_prob)/2.0 # Probability(stepping left) = prob(stepping right) = failure_prob value = [[collision_cost for col in range(len(grid[0]))] for row in range(len(grid))] policy = [[' ' for col in range(len(grid[0]))] for row in range(len(grid))] action = [-1, 0, 1] change = True while change: change = False for x in range(len(grid)): for y in range(len(grid[0])): if x == goal[0] and y == goal[1]: if value[x][y] > 0: value[x][y] = 0. policy[x][y] = '*' change = True elif grid[x][y] == 0: for i in range(len(delta)): v2 = 0. for a in [-1, 0, 1]: x2 = x + delta[(i + a) % 4][0] y2 = y + delta[(i + a) % 4][1] prob = 0. if a == 0: #shit this place!!!! prob = success_prob else: prob = failure_prob if x2 >= 0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]) and grid[x2][y2] == 0: v2 += value[x2][y2] * prob else: v2 += collision_cost * prob v2 += cost_step if v2 < value[x][y]: value[x][y] = v2 policy[x][y] = delta_name[i] change = True #print(x, y) return value, policy # --------------------------------------------- # Use the code below to test your solution # --------------------------------------------- grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 1, 0]] goal = [0, len(grid[0])-1] # Goal is in top right corner cost_step = 1 collision_cost = 1000 success_prob = 0.5 value,policy = stochastic_value(grid,goal,cost_step,collision_cost,success_prob) for row in value: print(row) for row in policy: print(row) # Expected outputs: # #[471.9397246855924, 274.85364957758316, 161.5599867065471, 0], #[334.05159958720344, 230.9574434590965, 183.69314862430264, 176.69517762501977], #[398.3517867450282, 277.5898270101976, 246.09263437756917, 335.3944132514738], #[700.1758933725141, 1000, 1000, 668.697206625737] # # ['>', 'v', 'v', '*'] # ['>', '>', '^', '<'] # ['>', '^', '^', '<'] # ['^', ' ', ' ', '^'] | cs |
정답은 위와 같다. 아래를 보면 예상되는 확률과 Policy가 나와 있는데,
1 2 3 4 5 6 7 8 9 | # ['>', 'v', 'v', '*'] # ['>', '>', '^', '<'] # ['>', '^', '^', '<'] # ['^', ' ', ' ', '^'] grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 1, 0]] | cs |
위 결과를 보면 애초에 장애물과 지도의 끝을 피하려는 경향을 보이는 것을 알 수 있다. 왜냐하면 장애물과 지도를 넘어가는 지점에 collision_cost = 1000 이렇게 엄청난 패널티를 부여했기 때문!!
1 2 3 4 5 6 7 8 9 10 11 12 13 | for a in [-1, 0, 1]: x2 = x + delta[(i + a) % 4][0] y2 = y + delta[(i + a) % 4][1] prob = 0. if a == 0: #shit this place!!!! prob = success_prob else: prob = failure_prob if x2 >= 0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]) and grid[x2][y2] == 0: v2 += value[x2][y2] * prob else: v2 += collision_cost * prob v2 += cost_step | cs |
주된 알고리즘은 위 부분이다. 원래 위치에서 로봇이 보고 있는 방향에 대해서 진행하려는 방향을 기준으로 앞과 양 옆을 탐색해야 한다. 즉, 총 3번 탐색을 해야 하고 for a in [-1, 0, 1]:
전진하려는 방향과 양 옆은 weight가 다르므로 이 예외 처리도 해준다.
, cost와 weight를 곱한 다음 모두 더해주고,
마지막으로 원래 1번 이동하기 위한 cost를 더하게 된다. v2 += cost_step
항상 강의를 마치고 나면 질의응답 시간이 있는데 다음과 같다.
Q : A* 알고리즘은 이미 지도상의 모든 요인들을 알고 있고 그들이 정적이라는 전제를 한다. 만약에 그렇지 않다면?? 그리고 실제 상황에서 우리는 지도를 가지고 있지도 않다. 이럴 때 쓸 수 있는 다른 알고리즘이 있는가??
A : A*는 정보를 모으고, 불확실성을 줄이는 과정을 할 수가 없다. 예를 들어서 내가 슈퍼에 간다고 할 때, 슈퍼까지 가는 최단 거리는 알 수 있지만, 내가 돈을 가지고 있는지 확인하고 다시 가는 그런 정보는 일절 다루지 않는다. outcome이 여러가지가 있을 경우를 다룰 수 없다는 것이다. 그래서 모든 경우에 대해서 dynamic programming을 하였던 것이다.
그런데 이것도 정도껏이지, 지도가 엄청나게 커져 버린다면 사실상 너무나 비효율적이다. 그래서 실제로는 Google Map같은 것을 이용해서 미리 계산된 최적의 경로를 조합하는 방식을 사용한다. 고맙게도 구글이 자신들의 지도를 가지고 실제로 이런 작업들을 미리 해 두었고, 우리는 쓰기만 하면 된다. 예를 들어,
- 서울에서 부산까지, 서울 - 이천 - 충주 - 구미 - 대구 - 밀양 - 부산 이렇게 간다고 할 때, 우리는 주요 도시들만 선택을 해 주고, 서울 - 이천 이렇게 가는 길은 이미 구글에서 최단 루트를 만들어 놓았다는 것이다. 그럼 A*는 왜 쓰냐, 그냥 구글신이 다 해주시는데? 이렇게 생각할 수가 있다. 그건 다음 질문에서도 또 나오는데 간략하게 말하자면 다음과 같다.
A*는 빠르다. 그리고 빨라야 한다. 서울 - 부산과 같은 큰 scale에서가 아니라, 당장 움직이는 차의 입장에서 앞에 차가 나타났거나, 신호가 바뀌는 등의 변화가 일어났을 때, A*를 이용해서 경로를 다시 설계한다. 이러한 방식이 빠르게 가능했고 실제로 사용했다고 한다.
Q : 실제 자율 주행 자동차에서는 경로를 어떻게 정했는가?
A : 앞서 말한 바와 같이 큰 스케일에서의 문제는 이미 구글 지도로 풀려있다고 가정을 한다, 이렇게 경로가 정해지면 모든 것들은 우리가 실습에서 했던 것과 같이 x, y, orientation, (velocity 실습에서는 안했지만)에 대한 문제가 된다.
Q : 실습에서 좌회전에 많은 패널티(=20)를 줬었는데, 실제로 그런 값을 어떻게 설정하는가?
A : 이 cost값을 설정할 때, 먼저 큰 범위에서 경로를 본 다음, 작은 범위로 더 자세하게 들여다봐서 옆에 차가 있는지 이런 것들을 살핀다. 큰 범위에서는 옆에 차가 움직인다 이런 것은 무시하고 정적이 상태를 가정한다. 이렇게 두 범위에서 관찰을 하면서 cost를 어떻게 설정해 주어야 할 지를 정하게 된다. 갑자기 옆 길이 막히기 시작했다, 이러면 차선 변경을 하지 않고 그 자리에서 기다리는 편이 좋을 것이다.
Q : 주차와 같이 목표가 여러 개인 경우는 어떻게 다룰 수 있는가?
A : 목표를 다수 지정해도 각각에 대해서 A*나 Dynamic programming 모두 적용할 수 있다. 해봐라.
Q : A*에서 Heuristic Function의 값들을 어떻게 설정하냐!! 여러 번 해보고 아는 것인가?
A : 다양한 방법들이 있지만, 하나 소개를 한다. 먼저, 원래 로봇을 움직이려면 x, y, orientation이 3개가 맞춰져야 하는데, 마지막 각도를 무시한 상태로 Heuristic Function을 짜 본다. 로봇에게 보다 자유를 주는 것이다. 그런 다음, 각도를 고려하지만, 장애물이 없다는 가정 하에 Heuristic Function을 짠다. 이제 이 두 가지 Heuristic Function을 상호 보완해서 알맞은(=Admissible) Heuristic Function을 찾는 방법이 있을 것이다. 이는 어디까지나 예제이고, 이런 식으로 로봇의 제약을 보다 풀어주어서 Heuristic Function을 찾을 수 있다는 것이다.
다음 강의는 쉽다. 그치만 중요하다. Control을 배우고 PID Control을 배운다!!
'공부' 카테고리의 다른 글
| 파이썬 - 리스트 중간 수정 (0) | 2019.01.16 |
|---|---|
| Control 공부했다. - PID Control (0) | 2019.01.08 |
| Search - 공부했다. (0) | 2019.01.05 |
| Particle Filter 공부했다 (2) (0) | 2019.01.02 |
| Particle Filter 공부했다. (0) | 2018.12.31 |
