Timeline for LPA* implementation keeps looping
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 11, 2018 at 21:34 | vote | accept | user149408 | ||
| Jun 6, 2018 at 12:32 | answer | added | user149408 | timeline score: 1 | |
| Jun 2, 2018 at 1:47 | comment | added | user149408 | @D.W. Thanks, that did indeed reveal that, at least in some cases, the function to calculate edge costs still returns the old values, not the new ones. Apparently I overlooked that the route graph is built from all configured maps, and if the map changes (traffic conditions are also map items), this information needs to be updated. Though that may not be the whole story, I need to fix this first. | |
| May 31, 2018 at 20:26 | comment | added | D.W.♦ | In this case I'm talking about a minimal graph (a minimal input), not minimal subset of code. | |
| May 31, 2018 at 20:04 | comment | added | user149408 | For concise pseudocode of generic LPA* see LPA* on Wikipedia. I authored the article, based on the paper cited, then based my implementation on it. Therefore, if I introduced any errors in the pseudocode, they would likely have propagated to the actual code. MCVE is difficult, as it is hard to separate the code in question from the rest of the application. | |
| May 31, 2018 at 18:33 | comment | added | D.W.♦ | I suggest using standard debugging techniques. Try to find a MCVE, specifically, a minimal-size graph that causes infinite looping. Once you've done that, look at the sequence of updates that get made to understand why a loop is happening. You can also try to write a proof that the algorithm should terminate. Then, if you're able to do that, check what invariants you found yourself using in that proof, and add asserts to your code to check that all of those invariants are true. Can you show concise pseudocode for LPA*? | |
| May 31, 2018 at 17:03 | history | asked | user149408 | CC BY-SA 4.0 |