Astar navigation unrecoverable deadlock

Question

question

EK asked Nov 7, '23 Jason Lightfoot commented Nov 14, '23

Astar navigation unrecoverable deadlock

Hi there, I understand that this is an ongoing challenge and may already be a feature under development but I wanted to check if anyone had cracked the Astar navigation unrecoverable deadlock problem since.

I am not very good in code but I tried copying a custom code prompt from the Kiva model to break task sequence to recalculate path and placed it to fire upon event triggered source. I have tried using different events but none appear to be suited to overcome my deadlock problem.

On A-Star block was firing a lot case as TE navigating on A-Star have its own logic to reroute around each other when blocked given a little time.

It seems that on A-star reroute does not just fire in a deadlocked event that brings the model to a stop but on other times either and it did not solve my problem.

I have also looked at the methods below:
Adjusting the travel nodes spacing does not work for me as it ended TE travelling between pallets in storage even though dynamic barriers have be implemented and I have conditional directions setup for each floor storage box

Reducing the number of travellers does not work for me as I am testing whether x number of TE will be able to handle my throughput in a given time

I have minimized my two direction travel, tested using an AGV network, tried adding an extra wide lane ( 2 travel nodes) in high traffic areas so TE can route around each other and tweaked with de-allocation times but I am still unable to run my model (12 hours) to completion.

Software Version:

FlexSim 23.2.2

deadlock astar collisions

· 4

Kavika F ♦ commented · Nov 07, 2023 at 09:43 PM

Hey @EK, if you haven't already read the documentation on how to prevent collisions and deadlock, I recommend you start there. It sounds like you've already implemented some things from there though. It would help us debug the issue if you gave us a model experiencing the deadlock you're describing. Thanks!

0 ·

EK Kavika F ♦ commented · Nov 08, 2023 at 01:42 AM

@Kavika F here is a simplified version of my model depicting the problem, the gridlock happens when there is a loaded TE in the storage bay that wants to travel downwards and another empty TE using that bay to travel upwards. Astar navigation gridlock.fsm

I have 3 layers of overlaid barriers with conditional directions and I have copied a set of these laid up side by side that you can see clearly.

I used alternating lanes to travel and up down storage slots for empty TE as part of traffic management logic as demonstrated in the Kiva model.

However when a TE is loaded, it can only travel out one direction

Do note that I added delays for 2 reasons. To compensate for turning delay as there is a stop for turns bug when used with elevator bank. To exacerbate my problem so that higher chance of unrecoverable deadlock happening for your reference. In my model that runs for 12 hours unrecoverable deadlock happens even without the delay.

Adjusting deallocation times will not be a solution for me in my use case. An adjustment to deallocation time sometimes results in additional hours of runtime and it's just lowering the probability of the problem happening.

PS: I have explored AGV networks extensively and even set up a control point at each entrance of my storage slots but overall it creates more problems than Astar navigation

Thanks for taking time to have a look at my model. Appreciate it!

0 ·

1699406447570.png (6.4 KiB)

1699406565990.png (3.1 KiB)

1699407159952.png (40.5 KiB)

astar-navigation-gridlock.fsm (240.2 KiB)

Jason Lightfoot ♦ EK commented · Nov 09, 2023 at 01:50 PM

Can you describe how it is meant to resolve the gridlock? At the moment the barrier direction constraints don't appear to allow any rerouting which suggests to me this scenario has to be avoided rather than resolved when it happens.

1 ·

Jason Lightfoot ♦ commented · Nov 14, 2023 at 03:02 PM

Hi @EK, was Jeanette F's answer helpful? If so, please click the "Accept" button at the bottom of their answer. Or if you still have questions, add a comment and we'll continue the conversation.

If we haven't heard back from you within 3 business days we'll auto-accept an answer, but you can always comment back to reopen your question.

0 ·

Answer 1 · 2023-11-09T16:40:36Z

Jeanette F answered Nov 9, '23

Hello @EK,

The TE are in deadlock because they can only travel into each other because of the rules of the barriers. To resolve this deadlock you would have to have the TE not fit the barriers constraints.

A way to do this would be to add that the barrier checks a blocked label on the TE. When the TE are blocked it changes this label making the TE not have to be constrained by the barrier and therefore be able to reroute. You could have another barrier with the constraint of the TE being blocked with a rule that TE follows that allows it to reroute.

In the following model there is no additional barrier. The TE will reroute not being constrained by the current barriers.

astar-navigation-gridlock_2.fsm

1699547969637.png (18.8 KiB)

1699548030529.png (17.6 KiB)

astar-navigation-gridlock-2.fsm (245.4 KiB)

question