How to reroute in AStar

Question

question

Steven Hamoen asked Jun 7, '18 Matthew Gillespie edited May 24, '19

How to reroute in AStar

@anthony.johnson Based on your remarks in this post I'm looking into the rerouting of taskexecuters in the AStar module. I tried with the following simple piece of process flow:

but it crashes Flexsim and corrupts the AStar module (I have send it to [email protected] already) I have attached the model but be carefull when running it.

So clearly this is not working. Considering the fact that there are 2 other events (OnAStarReroute and OnAStarContinue) it almost looks like there are particular functions or something to reroute?

So the question is: how to reroute? and when are those other 2 events fired?

exampleastar.fsm

Software Version:

FlexSim 18.1.1

astar on blocked rerouting

astarcrashing.png (181.5 KiB)

exampleastar.fsm (29.2 KiB)

Answer 1 · 2018-06-07T22:43:40Z

anthony.johnson answered Jun 7, '18 anthony.johnson edited Jun 7, '18

Yes, this is a bug. We'll get that fixed.

As for the events and when they fire:

1. OnBlocked - Fires when a traveler is attempting to claim a grid point, but is blocked by another traveler who has allocated the grid point.

2. OnContinue - Fires after a traveler has been blocked, when the disputed grid point is released by the blocking traveler. At that point the continuing traveler starts to move again on his path.

3. OnReroute - This will only fire when a traveler is blocked, and the blockage creates a deadlock situation. In this case the A* module has a canned solution, although I myself am somewhat dubious as to whether this solution works in all scenarios. We are already on iteration 2 of the canned solution. In iteration 1, we created a temporary barrier on all travelers currently blocked, then tested a reroute on all travelers in the deadlock cycle, and rerouted the "best" traveler based on a "best" decision heuristic. The problem with iteration 1 was that often times, especially in crowded situations, travelers got rerouted to paths that were so much longer than they needed to be. In iteration 2, we go through each traveler in the deadlock cycle, and see if they can move one grid up, down, to the left, or to the right. If we find one that works, we just tell that traveler to "step aside" that one grid unit, then continue to the destination. The traveler who steps aside will get his reroute event called. This seems to work better than iteration 1, because it will usually clear the deadlock without incurring too much travel penalty. But it is still not perfect. There are some deadlock scenarios where no one in the deadlock cycle can move, in which case it's "unrecoverable deadlock." For that we're thinking of maybe implementing "control areas" like in AGV land, where A* will only let a certain number of people into an area at a time, so you don't get into that situation. Anyway, my experience on this says we should avoid doing canned solutions when possible, because one size fits all just doesn't work often times. I'm even considering opening up the rerouting logic to the user, so they can roll their own even in deadlock situations. But that's not coming anytime too soon.

question