I began with a graph of 2D grid-world specifying the nodes and edges; and was given a start and goal. I was able to use A* to find the shortest path.
Now the problem was slightly modified in that concept of time was introduced and waiting at current node was allowed. The given problem can be considered with an exmaple as follows.
Suppose there are nodes in a linear world in form of an array a(1:6). Agent has to start at 2 and go to 6. As said before, i was able to plan this using A*. Optimal path is: 2->3->4->5->6.
But suppose now time enters the picture. Each transition like 3->4 means 1 time unit has passed. Agent begins moving at time t=0 and is told that it cannot go to node 5 at time t=3. So now the optimal path is: 2->3->4->4->5->6
But i am unable to think how to use A* to produce this plan. My idea was this: I will plan in 3 dimensions = (x,y,t) rather than just (x,y). A* can anyway handle any dimensions as long as graph structure is preserved.
however, i was confused because i know start as (2,0) where i use the convention (node, time). But what is the goal? I know it is something like: (6,t). But i don't know what t? So anytime i want to calculate my heuristic from a current node to the goal, I am stumped because i don't know what the goal is? How to handle this problem using A*. This example is only representative and highly simplified. I am working in 2D world but the problem is same as described in the example.
Citing some research paper where such problems are dealt will be very helpful but please try to avoid citing research that is clearly an overkill for this problem. If someone can give pseudocode that would be the best.
Since your model isn't completely dynamic and you know the changes beforehand, You can find your path by these simple changes to A* algorithm:
First when you expand a state you always consider that you can stay at that node.
Second when you are adding neighbors of a state to your fringe list you should check the constraints of the time and place you mentioned in your question:
state: position, time, h
current_state = priority_queue.top
priority_queue.add( state( current_state.position, current_state.time+1, new_h) )
for each neighbor of current state:
if possible to be at neighbor.position at current_state.time+1
priority_queue.add( state(neighbor.position, current_state.time+1, h) )
However if your world is completely dynamic you should implement a dynamic A* algorithm something like D*. Or you can run A* on the initial model and then whenever you encounter an obstacle in the middle of your path, you try to find a new path with A* while changing the map with respect to the obstacle.