2

I am trying to find the optimal path for a car from given
initial_state(of the form list[row,col,orientation]) to a given goal(of the form list[row,col]).

The car is free to move forward in directions (up, left, down, right).

It can perform 3 actions that are:
Turn Right and move Ahead(2), Move Ahead(1), Turn Left and move Ahead(20)
Note: numbers in bracket are the cost involved in performing respective action

Turning occurs in the same cell.
A 2D list (called grid) that consist of 0s and 1s is given as an input (a 2D non cyclic world).
0 --- navigable cell
1 --- non-navigable cell

The task is to find a path (with least cost) out of more than one possible paths.

Here is my code.

forward = [[-1,0],[0,-1],[1,0],[0,1]]
forward_name = ['up','left','down','right']
action = [-1,0,1]  ## turnRight, noTurn, turnLeft
action_name = ['R','#','L']
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]  ## for init[2]-- 0-up, 1-left, 2-down, 3-right 
goal = [2,0]
cost = [2,1,20]  ## turnRight, noTurn, turnLeft

def optimum_policy2D(grid, init, goal, cost):
    value = [[999*i for i in row] for row in grid]
    #print(value)
    r,c,orientation = init
    Routes = []   ##list of routes
    Routes.append([0,[init[:2]],orientation]) 
                   ## [cost,list of cell in the route,orientation]

    while [r,c]!=goal:
        presentRoute = Routes[0]
        for i in range(len(action)):
            dr, dc = forward[(presentRoute[2]+action[i])%4]
            if r+dr in range(len(grid)) and c+dc in range(len(grid[0])) and 
            value[r+dr][c+dc]!=999:
                thisRoute = presentRoute[:]
                thisRoute[1].append([r+dr,c+dc])
                thisRoute[0] += cost[i]
                thisRoute[2] = (thisRoute[2]+action[i])%4
                Routes.append(thisRoute[:])
        Routes = Routes[1:]
        Routes.sort()
        r,c = Routes[0][1][-1]
    print(Routes[0])

optimum_policy2D(grid, init, goal, cost)

I create a 2D list-value with an arbitrary high value 999 (higher than maximum cost involved) at cells which are non-navigable.

Next I create an empty-list (called Routes) which will store different routes. Each route will be of the form - [cost,list of cells in the route, final orientation of the car]. Before entering the while-Loop Route is initialised with initial state (as it will be part of any Route).

A for-Loop checks for valid neighbour (Validity of Neighbour - should be in the grid, should be navigable).

For a valid nieghbour-
create a copy of presentRoute in thisRoute.
append the new cell coordinates to the list of cells in the route.
update cost according to the action performed.
update the final orientation according to action.
*Finally append this new route to Routes.
(with each valid neighbour a new route is appended to Routes)

Routes[0] is now deleted. On sorting the Route,the first route in the list will be the the route with minimum cost. Variables 'r' and 'c' is updated with last cell of min-cost Route.

Once [r,c] is equal to the goal, we have found the route with minimum cost.

The output differs from my belief. I look for the mistakes in this code.

Community
  • 1
  • 1
Yash Raj
  • 21
  • 5
  • The code is a little beyond my level of understanding, but I would imagine for such small paths, you would do a path search, and then run your costs on it, e.g. from a given starting point, you check if there is more than 1 way you can traverse, and if so you append both to your Routes, you pick the first, and traverse until you have multiple options, and append inside the initial node list, so you end up with something like for Start 0,2,Goal 6,0 ,Routes = ["R","R","R",["D","D","End"],["U","U","R","R","Goal"],["R","R","U","U","Goal"]] – Reroute Jul 04 '18 at 14:07
  • I modified the code a little and it works. from copy import deepcopy – Yash Raj Aug 18 '18 at 07:14

0 Answers0