Problem 529229 · medium · Robotics · Level 05 Planning and Mapping

A* With Room to Spare

A* search · configuration space · Manhattan heuristic · occupancy grid

A round stock-taking robot crosses a warehouse. Its map is a list of strings grid, where grid[row][col] is '#' for a shelf and '.' for floor (row 0 at the top); a cell is a pair (row, col). The robot's centre moves from a cell to a neighbouring cell up, down, left or right, one move at a time.

The robot has a radius of radius cells, so its centre must keep clear of the shelves: a cell is usable only if it is floor and the distance from its centre to the centre of every shelf cell is more than radius:

\sqrt{(r_1 - r_2)^2 + (c_1 - c_2)^2} > \text{radius}

(side neighbours are 1 apart, corner neighbours \sqrt 2). Only '#' cells count as obstacles; the edge of the map does not.

Write plan_route(grid, radius, start, goal) that returns a route with the fewest moves from start to goal through usable cells, as a list of (row, col) tuples that begins with start and ends with goal. Several routes are often equally short: any of them is accepted. Return None if start or goal is not usable, or if no route exists. A route from a cell to itself is [start].

The tests hand your function to route_check(plan_route, grid, radius, start, goal) from the setup. It returns the number of moves of your route when the route is valid (so a valid but longer route shows a larger number than expected), None when you returned None, and otherwise a sentence that says what is wrong. The setup also provides aisles(rows, cols, seed, gap=3, clutter=0), a warehouse of long double shelves with openings gap cells wide, which the larger tests use; try print("\n".join(aisles(20, 30, 1))) with Run.

Examples

Input:  grid = ["......",
                "......",
                "..##..",
                "......",
                "......"], radius = 1, start = (4, 0), goal = (0, 5)
Output: a route of 9 moves, for example
        [(4, 0), (3, 0), (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
Explanation: the cells side by side with the shelf are not usable, but the
corner cells such as (1, 1) are (1.414 > 1). The tests report 9.

Input:  grid = ["....#....",
                "....#....",
                ".........",
                "....#....",
                "....#...."], radius = 1, start = (2, 0), goal = (2, 8)
Output: None
Explanation: the doorway (2, 4) is exactly 1 away from the shelves above and below it.

Input:  the same grid with radius = 0.5
Output: [(2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8)]
Explanation: a slimmer robot fits through. The tests report 8.

Constraints

  • all rows have the same length; start and goal are inside the grid
  • grids up to 60 by 60: a search that wanders over the whole map many times is too slow

Goals

  • Plan a shortest route for a round robot by searching the inflated map
  • Guide the search towards the goal with an admissible heuristic
  • Return the route itself, start and goal included, or `None` when there is none
Starting Python…