gavinphr / space-time-astar Goto Github PK

The LICENSE.txt file ends with a space character.
The image file within the fig directory contains an asterisk.

These make it difficult to check out this repo on Windows, as they are not legal file names.

Hello,

I notice that my agent will avoid the entire obstacle path for the full time interval. Shouldn't it only avoid the obstacle's path at each instant in time?

For example, a simple case that is currently infeasible.

X = dynamic obstacle
G = Goal
A = Agent
O = empty space

Time = 0
OOOOO
AOGOX
OOOOO
Time = 1
OOOOO
OAGXO
OOOOO

What should happen next
Time = 2
OOOOOO
OOGXOO (G and X occupy same pos)
OOAOOO

Time = 3
OOOOOO
OXGAOO (G and A occupy same pos: Finsihed)
OOOOOO

It only matters that the agent avoids colliding with the obstacle at each instant in time. Not for the full trajectory of the obstacle.
I have a matplotlib visualizer I would be happy to share if you believe it would help explain!

@GavinPHR Thank you for your work this is very interesting!

Hi, thanks for the repository. Is it possible to share an example code where trajectory of at least one of the robots is known, along with static obstacle? I am unable to find a good resource on how to use this repository really. Thanks

Can you give me an example about how to use it? I will get a bug when I call this lib.

Consider this example:

    grid_size, cell_size, domain_size = 20, 1, 1
    
    static_obstacles = [(0, 0), (10, 8), (10, 10), (10, 12), (12, 12), (grid_size-1, grid_size-1)]
    
    dynamic_obstacles = {}    
    for seed in (8, 10, 16, 18):  # create dynamic obstacles
        random.seed(seed)    
        x0, y0, x1, y1 = [random.randint(2, grid_size-3) for _ in (0, 1, 2, 3)]
        start, goal = (x0, y0), (x1, y1)
        planner = Planner(cell_size, domain_size, static_obstacles)
        path = planner.plan(start, goal, dynamic_obstacles)
        for step, coord in enumerate(path):
            if step not in dynamic_obstacles:
                dynamic_obstacles[step] = []
            dynamic_obstacles[step].append(coord)

    start, goal = (3, 3), (17, 17)
    planner = Planner(cell_size, domain_size, static_obstacles)
    path = planner.plan(start, goal, dynamic_obstacles, debug=True)
    
    print(path)

Path plan found after 43 iterations (works as expected):

[[3 3] [4 4] [5 5] [6 5] [7 6] [8 7] [8 8] [8 9] [8 10] [8 11] [7 12] [8 13] [9 14] [10 15] [11 16] [12 17] [13 17] [14 17] [15 17] [16 17] [17 17]]

Now I just remove the static obstacle at (10, 10), everything else remains the same:

    grid_size, cell_size, domain_size = 20, 1, 1
    
    static_obstacles = [(0, 0), (10, 8), (10, 12), (12, 12), (grid_size-1, grid_size-1)]
    
    dynamic_obstacles = {}    
    for seed in (8, 10, 16, 18):  # create dynamic obstacles
        random.seed(seed)    
        x0, y0, x1, y1 = [random.randint(2, grid_size-3) for _ in (0, 1, 2, 3)]
        start, goal = (x0, y0), (x1, y1)
        planner = Planner(cell_size, domain_size, static_obstacles)
        path = planner.plan(start, goal, dynamic_obstacles)
        for step, coord in enumerate(path):
            if step not in dynamic_obstacles:
                dynamic_obstacles[step] = []
            dynamic_obstacles[step].append(coord)

    start, goal = (3, 3), (17, 17)
    planner = Planner(cell_size, domain_size, static_obstacles)
    path = planner.plan(start, goal, dynamic_obstacles, debug=True)
    
    print(path)

Path plan found after 28 iterations (weird things happen at t=8):

[[3 3] [4 4] [5 5] [6 4] [7 5] [8 6] [9 6] [10 6] [11 6] [2 17] [3 17] [4 17] [5 17] [6 17] [7 17] [8 17] [9 17] [10 17] [11 17] [12 17] [13 17] [14 17] [15 17] [16 17] [17 17]]

Any ideas on this?

• Python 3.8.9
• scipy 1.6.2
• numpy 1.20.2

In a grid map, are static obstacle shapes the corresponding grid? Do the coordinates refer to the coordinates of the center of the obstacle, which is also the center of the grid?
By analyzing the code of the Grid class, the grid map is based on the largest rectangle formed by static obstacles as the boundary. However, in details, there are some small problems in the conversion of coordinates and grids. For example,

• grid_size=100
• the center coordinates of the leftmost obstacle are [0, 0]
• the center coordinates of the rightmost obstacle are [1000,0]
  At this time,
• minx=0, maxx=1000, x_size= (1000 - 0) // 100 = 10,
  so the grid map has 10 horizontal cells, but there are actually 11, which are (0,0), (100,0), ..., (1000, 0).