Path hunting with Z3 solver

Question

I am modeling below problem in Z3. The aim is to find the path for Agent to reach the coin avoiding obstacles.

Initial_grid =[['T' 'T' 'T' 'T' 'T' 'T' 'T']
              ['T' ' ' ' ' ' ' ' ' ' ' 'T']
              ['T' ' ' 'A' 'O' ' ' 'O' 'T']
              ['T' 'O' ' ' ' ' ' ' ' ' 'T']
              ['T' ' ' ' ' 'O' 'O' 'C' 'T']
              ['T' ' ' ' ' ' ' ' ' ' ' 'T']
              ['T' 'T' 'T' 'T' 'T' 'T' 'T']]

x, y = Ints('x y')
x = agent_loc[0]
y = agent_loc[1]

xc, yc = Ints('xc yc')
xc = coin_loc[0]
yc = coin_loc[1]

s = Solver()
s.add(x,y = (Or(move_right(),move_left(),move_top(),move_bottom())))
solve(And (x = xc) (y = yc))
if s.check() == unsat:
      print('Problem not solvable')
else:
    m = s.model()

I added constraint for movement function which returns x,y coordinates if the movement is valid (no obstacles and within boundary) and returns false otherwise. How can I model the movement constraint as the one in code gives error: add() got an unexpected keyword argument 'y'.

Answer 1

One way to think about these sorts of search problems is a two pronged approach:

• Can I find a path with 1 move? If not, try with 2 moves, 3 moves, etc. till you hit an upper bound and you decide to stop trying.

• Instead of "searching," imagine a path is given to you; how would you check that it's a good path? The magic of SMT solving is that if you can write a program that verifies a given "alleged" solution is good, it can find you one that is indeed good.

The following is a solution to your problem following these lines of thought.

from z3 import *

Grid = [ ['T', 'T', 'T', 'T', 'T', 'T', 'T']
       , ['T', ' ', ' ', ' ', ' ', ' ', 'T']
       , ['T', ' ', 'A', 'O', ' ', 'O', 'T']
       , ['T', 'O', ' ', ' ', ' ', ' ', 'T']
       , ['T', ' ', ' ', 'O', 'O', 'C', 'T']
       , ['T', ' ', ' ', ' ', ' ', ' ', 'T']
       , ['T', 'T', 'T', 'T', 'T', 'T', 'T']
       ]

Cell, (Wall, Empty, Agent, Obstacle, Coin) = EnumSort('Cell', ('Wall', 'Empty', 'Agent', 'Obstacle', 'Coin'))

def mkCell(c):
    if c == 'T':
        return Wall
    elif c == ' ':
        return Empty
    elif c == 'A':
        return Agent
    elif c == 'O':
        return Obstacle
    else:
        return Coin

def grid(x, y):
    result = Wall
    for i in range (len(Grid)):
        for j in range (len(Grid[0])):
            result = If(And(x == IntVal(i), y == IntVal(j)), mkCell(Grid[i][j]), result)
    return result

def validStart(x, y):
    return grid(x, y) == Agent

def validEnd(x, y):
    return grid(x, y) == Coin

def canMoveTo(x, y):
    n = grid(x, y)
    return Or(n == Empty, n == Coin, n == Agent)

def moveLeft(x, y):
    return [x, If(canMoveTo(x, y-1), y-1, y)]

def moveRight(x, y):
    return [x, If(canMoveTo(x, y+1), y+1, y)]

def moveUp(x, y):
    return [If(canMoveTo(x-1, y), x-1, x), y]

def moveDown(x, y):
    return [If(canMoveTo(x+1, y), x+1, x), y]

Dir, (Left, Right, Up, Down) = EnumSort('Dir', ('Left', 'Right', 'Up', 'Down'))

def move(d, x, y):
    xL, yL = moveLeft (x, y)
    xR, yR = moveRight(x, y)
    xU, yU = moveUp   (x, y)
    xD, yD = moveDown (x, y)
    xN     = If(d == Left, xL, If (d == Right, xR, If (d == Up, xU, xD)))
    yN     = If(d == Left, yL, If (d == Right, yR, If (d == Up, yU, yD)))
    return [xN, yN]

def solves(seq, x, y):
    def walk(moves, curX, curY):
        if moves:
            nX, nY = move(moves[0], curX, curY)
            return walk(moves[1:], nX, nY)
        else:
            return [curX, curY]

    xL, yL = walk(seq, x, y)
    return And(validStart(x, y), validEnd(xL, yL))

pathLength = 0

while(pathLength != 20):
    print("Trying to find a path of length:", pathLength)

    s    = Solver()
    seq  = [Const('m' + str(i), Dir)  for i in range(pathLength)]
    x, y = Ints('x y')
    s.add(solves(seq, x, y))

    if s.check() == sat:
        print("Found solution with length:", pathLength)
        m = s.model()
        print("    Start x:", m[x])
        print("    Start y:", m[y])
        for move in seq:
             print("    Move", m[move])
        break
    else:
        pathLength += 1

When run, this prints:

Trying to find a path of length: 0
Trying to find a path of length: 1
Trying to find a path of length: 2
Trying to find a path of length: 3
Trying to find a path of length: 4
Trying to find a path of length: 5
Found solution with length: 5
    Start x: 2
    Start y: 2
    Move Down
    Move Right
    Move Right
    Move Right
    Move Down

So, it found a solution with 5 moves; you can chase it in your grid to see that it's indeed correct. (The numbering starts at 0,0 at the top-left corner; increasing as you go to right and down.) Additionally, you’re guaranteed that this is a shortest solution (not necessarily unique of course). That is, there are no solutions with less than 5 moves.

I should add that there are other ways to solve this problem without iterating, by using z3 sequences. However that’s even more advanced z3 programming, and likely to be less performant as well. For all practical purposes, the iterative approach presented here is a good way to tackle such search problems in z3.

Answer 2

An alternative solution:

from z3 import *
#          1    2    3    4    5    6    7
Grid = [ ['T', 'T', 'T', 'T', 'T', 'T', 'T']  #  1
       , ['T', ' ', ' ', ' ', ' ', ' ', 'T']  #  2
       , ['T', ' ', 'A', 'O', ' ', 'O', 'T']  #  3
       , ['T', 'O', ' ', ' ', ' ', ' ', 'T']  #  4
       , ['T', ' ', ' ', 'O', 'O', 'C', 'T']  #  5
       , ['T', ' ', ' ', ' ', ' ', ' ', 'T']  #  6
       , ['T', 'T', 'T', 'T', 'T', 'T', 'T']  #  7
       ]

rows = len(Grid)
Rows = range(rows)
cols = len(Grid[0])
Cols = range(cols)
Infinity = rows * cols + 1

deltaRow = [-1,  0, +1,  0]
deltaCol = [ 0, -1,  0, +1]
delta    = ['up', 'left', 'down', 'right']
deltaInv = ['down', 'right', 'up', 'left'];
Deltas = range(len(delta))

s = Solver()

#  2D array comprehension: 
#  create matrix of path distances
#  https://stackoverflow.com/a/25345853/1911064
distances = [[Int('d'+str(r)+'_'+str(c)) for c in Cols] for r in Rows]

# http://www.hakank.org/z3/z3_utils_hakank.py
# v is the minimum value of x
def minimum(sol, v, x):
  sol.add(Or([v == x[i] for i in range(len(x))])) # v is an element in x)
  for i in range(len(x)):
    sol.add(v <= x[i]) # and it's the smallest

#  constraints for distances
for row in Rows:
    for col in Cols:
        #  shorthands to reduce typing
        g = Grid[row][col]
        dist = distances[row][col]
        if (g == 'T') or (g == 'O'):
           #  obstacles and walls cannot be part of the path
           s.add(dist == Infinity)
        elif g == 'A':
           #  the path starts here
           s.add(dist == 0)
        else:
           #  array index violations cannot happen
           #  because the wall case is handled above
           minimum(s, dist, [distances[row + deltaRow[i]][col + deltaCol[i]] + 1 for i in Deltas])
           #  remember the coin coordinates
           if g == 'C':
               rowCoin, colCoin = row, col
               #  detect unreachable target as UNSAT
               s.add(dist < Infinity)
                    
if s.check() == sat:
    #  show the resulting path
    m = s.model()
    row, col = rowCoin, colCoin
    #  collect the path in reverse to
    #  avoid dead-ends which don't reach the coin
    path = []
    dir =  []
    while True:
        path.insert(0, [row, col])
        if Grid[row][col] == 'A':
            break
        neighborDistances = [m[distances[row+deltaRow[i]][col+deltaCol[i]]].as_long() 
                             for i in Deltas]
        best = neighborDistances.index(min(neighborDistances))
        #  advance to the direction of the lowest distance
        row += deltaRow[best]
        col += deltaCol[best]
        dir.insert(0, best)

    print('start ' + ' [row ' + str(path[0][0]+1) + '; col ' + str(path[0][1]+1) + ']')
    for i in range(1, len(path)):
        print(deltaInv[dir[i-1]].ljust(6) + ' [row ' + str(path[i][0]+1) + '; col ' + str(path[i][1]+1) + ']')
else:
     print("No path found!")