1、什麼是動態規劃
CS專業出身的人大抵沒有人不知道動態規劃(Dynamic Programming)的，該算法的本質就是把複雜的大問題分解成相互重疊的簡單子問題，將子問題的最優解層層組合起來，就得到了複雜大問題的最優解。
能用動態規劃解決的問題必須滿足兩個條件：一是最優的結構。即問題的最優解所包含的子問題的解也是最優的；二是子問題相互重疊。即是當使用遞歸進行自頂向下的求解時,每次產生的子問題不總是新的問題,而是已經被重複計算過的問題。
最典型的經常被拿來講解Dynamic Programming的例子就是斐波那契數列(Fibonacci sequence)，它的數學定義如下:
<code>F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)/<code>
可以看到斐波那契數列(Fibonacci sequence)帶有明顯的子問題拆分的特徵，通過將F(n)的求解拆分為F(n-1)和F(n-2)兩個子問題，重複的子問題只需要計算一次。
<code>F(0) = 0
F(1) = 1
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)
.../<code>
斐波那契數列(Fibonacci sequence)計算的Python實現如下：
<code>def fib(n):
f = [0] * (n + 1)
f[0] = 0
f[1] = 1
for i in range(2, n + 1):
f[i] = f[i - 1] + f[i - 2]
return f[n]/<code>
2、動態規劃算法在自動駕駛中的應用
在如下的自動駕駛場景中，無人車在位置A處進行右轉，目標是達到位置G處。理想的駕駛路徑是:
(位置A處右轉)->(進入車道C)->(變道進入車道B)->(左轉到達目標位置G)。
自動駕駛場景
但是由於環境是隨機的，我們的無人車在實際上路時，可能遇到各種情況。比如當我們計劃從車道C變道進入車道B時，發現左側被一輛大卡車擋住了；如果停下來等大卡車駛過之後再變道，會被車道C上無人車後方的司機拼命用大喇叭催你，無奈之下，我們只好放棄左轉，繼續直行，再尋求其它路徑達到目的地。
目標車道被阻塞的場景
所以最後的行駛路徑可能就變成了:
(位置A處右轉)->(進入車道C，直行)->(通過路口，進入車道D)->(連續右轉，達到位置E)->(直行到達目標位置G)
這裡可以看到，我們需要一種方法，使得在無人車放棄車道C到車道B的變道時繼續前進時，能夠快速找到下一條可通行路徑。動態規劃(Dynamic Programming)可以用來解決這類問題，它可以給出從任意一個位置出發到達目的地的最優路徑。
2.1、簡化的問題
為了應用動態規劃(Dynamic Programming)算法，我們首先看下簡化版的問題。如下圖所示，我們將道路區域按照空間進行網格劃分，帶陰影線的網格表示不可通行區域，G表示目標位置。
圖中的藍色箭頭表示車輛在該位置的規劃策略，也是我們要求解的目標，可以認為我們的目標就是通過Policy函數，將位置(x，y)映射到車輛的運動Action上。簡化起見，我們假設車輛只有四個運動Action：向上、向下、向左、向右。
<code>Policy(x, y) = Action{left, right, up, down}/<code>如何將(x,y)轉化為具體的Action呢？ 為了計算Action，我們首先需要為每個網格計算Value值。Value的大小與該網格距離目標位置的最短距離成正比。有了Value值之後，Action的方向就是從Value值大的網格指向Value值小的網格。
2.2 網格Value的計算
每個Cell的Value的Value Function定義如下：
(x’, y‘)的取值為: (x-1, y),(x, y-1), (x+1, y), (x, y+1)，即它的左、上、右、下四個方向的Cell； cost為Cell之間的Cost，這裡取Cost為步長1。
可以看到，這是一個典型的動態規劃的問題。我們看下如何使用動態規劃(Dynamic Programming)算法求解每個Cell的Value。
<code># Map Represention
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]
# the cost associated with moving from a cell to an adjacent one
cost = 1
delta = [[-1, 0 ], # go up
[ 0, -1], # go left
[ 1, 0 ], # go down
[ 0, 1 ]] # go right
def compute_value(grid,goal,cost):
# If a cell is a wall or it is impossible to reach the goal from a cell,assign that cell a value of 99.
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]
print((x2, y2))
if x2 >= 0 and x2 = 0 and y2 v2 = value[x2][y2] + cost
if v2 change = True
value[x][y] = v2
return value/<code>
最後我們可以得到如下的Value值，通過它可以得到從任意位置到達目標位置的最短距離。
<code>[[11, 99, 7, 6, 5, 4],
[10, 99, 6, 5, 4, 3],
[9, 99, 5, 4, 3, 2],
[8, 99, 4, 3, 2, 1],
[7, 6, 5, 4, 99, 0]]/<code>
將Value值映射為Policy，最終輸出的結果如下：
<code> [['v', ' ', 'v', 'v', 'v', 'v'],
['v', ' ', 'v', 'v', 'v', 'v'],
['v', ' ', 'v', 'v', 'v', 'v'],
['v', ' ', '>', '>', '>', 'v'],
['>', '>', '^', '^', ' ', '*']]/<code>
2.3 應用到車輛運動中
仍然以簡化的方式來展示Dynamic Programming的應用。如下圖所示，紅色是車輛的當前位置，藍色是車輛的目標姿態。假設車輛的運動角度theta只有四個選擇{Up, Down, Left, Right}， 車輛的運動只有三個選擇: 左轉、直行、右轉。
我們首先構建地圖信息：
<code># 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]]/<code>
給定車輛的起始位置、結束位置和車輛的運動約束：
<code>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]
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']
cost = [2, 1, 2] # cost has 3 values, corresponding to making a right turn, no turn, and a left turn/<code>
基於Dynamic Programming計算從起點到終點的車輛運動路徑。
<code>def optimum_policy2D(grid,init,goal,cost):
value = [[[999 for row in range(len(grid[0]))] for col in range(len(grid))],
[[999 for row in range(len(grid[0]))] for col in range(len(grid))],
[[999 for row in range(len(grid[0]))] for col in range(len(grid))],
[[999 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))],
[[' ' for row in range(len(grid[0]))] for col in range(len(grid))],
[[' ' for row in range(len(grid[0]))] for col in range(len(grid))],
[[' ' for row in range(len(grid[0]))] for col in range(len(grid))]]
policy2D = [[' ' 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])):
for orientation in range(4):
if goal[0] == x and goal[1] == y:
if value[orientation][x][y] > 0:
value[orientation][x][y] = 0
policy[orientation][x][y] = '*'
change = True
elif grid[x][y] == 0:
for i in range(3):
o2 = (orientation + action[i]) % 4
x2 = x + forward[o2][0]
y2 = y + forward[o2][1]
if x2 >= 0 and x2 = 0 and y2 v2 = value[o2][x2][y2] + cost[i]
if v2 value[orientation][x][y] = v2
policy[orientation][x][y] = action_name[i]
change = True
x = init[0]
y = init[1]
orientation = init[2]
policy2D[x][y] = policy[orientation][x][y]
while policy[orientation][x][y] != '*':
if policy[orientation][x][y] == '#':
o2 = orientation
elif policy[orientation][x][y] == 'R':
o2 = (orientation - 1) % 4
elif policy[orientation][x][y] == 'L':
o2 = (orientation + 1) % 4
x = x + forward[o2][0]
y = y + forward[o2][1]
orientation = o2
policy2D[x][y] = policy[orientation][x][y]
return policy2D/<code>
最終輸出的路徑結果如下:
<code>[[' ', ' ', ' ', 'R', '#', 'R'],
[' ', ' ', ' ', '#', ' ', '#'],
['*', '#', '#', '#', '#', 'R'],
[' ', ' ', ' ', '#', ' ', ' '],
[' ', ' ', ' ', '#', ' ', ' ']]
/<code>
在上面的實現中，我們將左轉的Cost設置為20，比較高的左轉代價使得車輛更傾向於直行和右轉，所以規劃路徑的效果如下：
我們將左轉的Cost降低到2，看看會發生什麼效果？
<code>[[' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' '],
['*', '#', '#', 'L', ' ', ' '],
[' ', ' ', ' ', '#', ' ', ' '],
[' ', ' ', ' ', '#', ' ', ' ']]/<code>
可以看到，路徑規劃在路口位置選擇了左轉，規劃效果如下：
1、Dynamic Programming - Artificial Intelligence for Robotics，https://www.youtube.com/watch?v=r2bPY2s9wII&t=12s
閱讀更多 半杯茶的小酒杯 的文章
