Astar navigation unrecoverable deadlock

Question

question

EK asked Nov 07 2023 at 6:04 PM Jason Lightfoot commented Nov 14 2023 at 3:02 PM

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 9: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 1: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 1: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 3: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 ·

______

Cookie preferences

Your privacy is important to us and so is an optimal experience. To help us customize information and build applications, we collect data about your use of this site.

May we collect and use your data?

Learn more about the Third Party Services we use and our Privacy Statement.

Strictly necessary – required for our site to work and to provide services to you

These cookies allow us to record your preferences or login information, respond to your requests or fulfill items in your shopping cart.

YES

Improve your experience – allows us to show you what is relevant to you

These cookies enable us to provide enhanced functionality and personalization. They may be set by us or by third party providers whose services we use to deliver information and experiences tailored to you. If you do not allow these cookies, some or all of these services may not be available for you.

YES

NO

Customize your advertising – permits us to offer targeted advertising to you

These cookies collect data about you based on your activities and interests in order to show you relevant ads and to track effectiveness. By collecting this data, the ads you see will be more tailored to your interests. If you do not allow these cookies, you will experience less targeted advertising.

YES

NO

Are you sure you want a less customized experience?

We can access your data only if you select "yes" for the categories on the previous screen. This lets us tailor our marketing so that it's more relevant for you. You can change your settings at any time by visiting our privacy statement

Your experience. Your choice.

We care about your privacy. The data we collect helps us understand how you use our products, what information you might be interested in, and what we can improve to make your engagement with Autodesk more rewarding.

May we collect and use your data to tailor your experience?

Explore the benefits of a customized experience by managing your privacy settings for this site or visit our Privacy Statement to learn more about your options.

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

Jeanette F answered Nov 09 2023 at 4:40 PM

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