Details
-
Improvement
-
Resolution: Unresolved
-
Major
-
CheshireCat.Next
-
None
-
1
Description
Planner currently stops iterating when one of the following is achieved:
- Estimated cost falls below a fixed threshold t, or
- A fixed maximum number of iterations i is reached
There are some problems with this approach. Let c be the (unknown) optimal cost.
- If c << t, Planner will stop too early based on reaching t, even though much improvement is still possible.
- If c > t, Planner will iterate the full i iterations even if it is no longer making progress.
A better stopping criterion is to calculate a trailing average proportional cost improvement per iteration p over the last 1,000 iterations (= sample size for "how much improvement is still being achieved") and replacing t with an "epsilon" value e based on this metric, so Planner would instead stop when one of the following is achieved:
- p for the last 1,000 iterations falls below e
- A fixed maximum number of iterations i is reached
Using this approach, Planner would not stop too early if it was still making good progress, nor would it continue to iterate futilely if only minimal or no progress was still being made.