How to find shortest route between points using AI?

Question

I am trying to improve my AI knowledge by attempting problems on hackerrank.

One of the problem is:

Princess Peach is trapped in one of the four corners of a square grid. You are in the center of the grid and can move one step at a time in any of the four directions. Can you rescue the princess?

Details are here.

I needed a hint to go about this problem in a systematic way. Is it the case of the shortest route problem? Or which algorithms/concepts of AI can be used to solve this problem?

Thanks.

score 3 · Accepted Answer · edited May 23 '17 at 12:07

3

This is shortest path problem, where nodes are cells in the grid, and edges are possible moves from cell to cell.

Simplest solution to it is using a BFS (since the graph is unweighted). An improvement is using a bi-directional BFS.

An AI oriented improvement is to use an informed algorithm such as A*. You are going to need an admissible heuristic function to use it, can you think of any? (There is a classic well known one, but I'll let you figure it out on your own).

edited May 23 '17 at 12:07

Community

1
1

answered Jun 26 '15 at 07:39

amit

175,853
27
231
333

Thanks Amit.... I think admissible heuristic function should be monotonic or consistent heuristic. – Omkar Shetkar Jun 26 '15 at 09:48
@omkar But what should it be? Given a point `(x1,y1)`, and a known target point `(x2,y2)` - what will your heuristic be on this grid? Think about a simpler problem (without obstacles maybe?) and how long will it take to move from one to the other in the simpler problem. That could be your heuristic. – amit Jun 26 '15 at 10:00
Initially I tried it with BFS and it worked! Then plugged in heuristic function h(n) of smallest distance between given point and goal point. That is, |x1-x2|+|y1-y2|. It seems to be known as Manhattan distance. By this I can guide the search relatively better. – Omkar Shetkar Jun 29 '15 at 05:54

score 0 · Answer 2 · answered Dec 11 '15 at 10:01

A bit late, but out of curiosity i tried this in php by first getting the location of the princess, then the location of mario follwed by a loop to move Mario around. This wins the game but it's not the fastest way, especially when the grid is big.

        function displayPathtoPrincess($m, $grid) {
            //get mario and princesses locations
            $gridstring = implode('', $grid);
            $p = strpos($gridstring, 'p') + 1;
            $m = strpos($gridstring, 'm') + 1;

            $positioncount = 0;

            //get marios and princess xy location
            for ($x = 0; $x < count($grid); $x ++) {
                for ($y = 0; $y < count($grid); $y ++) {
                    $positioncount ++;
                    if ($positioncount == $m) {
                        $mario[0] = $x;
                        $mario[1] = $y;
                    }

                    if ($positioncount == $p) {
                        $princess[0] = $x;
                        $princess[1] = $y;
                    }

                    if (isset($mario) > 0 && isset($princess) > 0)
                        break;
                }
            }


        //Find princess
            $moves = '';
            for ($x = 0; $x < count($grid); $x ++) {
                for ($y = 0; $y < count($grid); $y ++) {
                    //if at marios location ...

                    if ($mario[0] == $x && $mario[1] == $y) {
                        $updownmove = $princess[0] - $mario[0];

                        if ($updownmove < 0) {
                            for (; $updownmove < 0; $updownmove++) {
                                $newposition = $mario[0] - 1;
                                if ($newposition >= 0) {
                                    $mario[0] = $newposition;

                                    if (trim($moves) != '') {
                                        $moves .= "\n";
                                    }
                                    $moves .= "UP";
                                }
                            }
                        } else {
                            for (; $updownmove > 0; $updownmove--) {
                                $mario[0] = $mario[0] + 1;
                                if (trim($moves) != '') {
                                    $moves .= "\n";
                                }
                                $moves .= "DOWN";
                            }
                        }

                        $rightleftmove = $princess[1] - $mario[1];
                        if ($rightleftmove < 0) {
                            for (; $rightleftmove < 0; $rightleftmove++) {
                                $newposition = $mario[1] - 1;
                                if ($newposition >= 0) {
                                    $mario[1] = $newposition;

                                    if (trim($moves) != '') {
                                        $moves .= "\n";
                                    }
                                    $moves .= "LEFT";
                                }
                            }
                        } else {
                            for (; $rightleftmove > 0; $rightleftmove--) {
                                $mario[1] = $mario[1] + 1;
                                if (trim($moves) != '') {
                                    $moves .= "\n";
                                }
                                $moves .= "RIGHT";
                            }
                        }
                    }

                    if (isfound($mario, $princess)) {
                        echo $moves;
                        return;
                    }
                }
            }
        }

        function isfound($mario, $princess) {
            if (count($mario) == 0)
                return false;
            if (($mario[0] == $princess[0]) && ($mario[1] == $princess[1])) {
                return true;
            } else {
                return false;
            }
        }

score 0 · Answer 3 · answered Sep 01 '17 at 13:31

Load in the input data, starting with the grid size.
Accept lines of input corresponding to the grid size.
Since you know that the grid is a square, check the corners and move diagonally corresponding to what corner the princess is in.

Solution in 7 lines of python:

gridsize  = int(input('Enter number of rows: '))
grid      = [ input('Enter row: ') for r in range(gridsize) ]
move_dist = (gridsize-1)//2
if   grid[ 0][ 0] == 'p': print('\n'.join([   'UP\nLEFT'] * move_dist))
elif grid[ 0][-1] == 'p': print('\n'.join([  'UP\nRIGHT'] * move_dist))
elif grid[-1][ 0] == 'p': print('\n'.join([ 'DOWN\nLEFT'] * move_dist))
elif grid[-1][-1] == 'p': print('\n'.join(['DOWN\nRIGHT'] * move_dist))

How to find shortest route between points using AI?

3 Answers3