Organization of the Step Optimization
Here is an attempt to sort the questions, ideas and what we look at closer for the Nelder Mead. The aim is to be more efficient for discussion.
If you want to add/change stuff: update this post and do not comment (to keep the structure).
Optimisation on Disk
xref #229 for profiling results, and discussion.
Ideas to have efficient code at Vadere's computational bottleneck:
- try other algorithms (other classes or ones that require less evaluations, such as derivative based)
- use minimum of start positions (white-box instead of black-box)
- use surrogate model, or simplify problem such that we get a close solution
- the neighboring pedestrians have almost zero potential contribution use smaller cut-off radius
- use voronoi / Delaunay triangulation
- decision rule, when to optimize only on the circle (1D problem) and when inside the circle (2D)
- Correct/better(?) handling of constrains (e.g. restrict the searching in an obstacle to a minimum). General approaches:
- constant penalty term (current implementation)
- increasing penalty (the further I go into illegal area, the larger is the penalty -> provides derivative back into the legal area)
- projection methods to get back into legal area
- calibration of threshold(s) (convergence plots)
Quality of solution:
For now we assume, that we want to find the global minimum. However, this may not always be the "best" from a modelling perspective (see also next point)
- Use a metric to compare "true" solution (-> Brute Force) and found solution by the algorithm
- Look at different cases:
- Obstacles around
- High density
- Single ped (cf. S2UCRE scenario used so far)
- different geodesic trajectories between source <-> target (diagonal, U-form, straight line)
- correct calibration of threshold -> when is a solution good enough
- Nelder Mead seems to have trouble to find a solution at the circle.
- One guess is that due to the stepcircle constrain, the simplex has troubles to "walk along the circle" once it is at the stepcircle radius
- calibration: if we use a black-box start value setting: how many times do we have to start an optimization to have a high probability to find the desired solution?
Due to non-linearity, there is no guarantee that we find the true solution. But if we assume we can select it, in some cases the true solution is not the "best" one from a modelling approach.
- What if there are multiple patches with local minima (non-convex)
- E.g. do we take the closer one to the pedestrian?
- Is the patch with the global minimum always better than the other minima?
- What if the minima are almost identical, which one do we choose?
- The most troubles seem to be in high density scenarios as we have the "most non-linearity" there
- Do we want overlapping-free solutions?
- This impacts the way we view pedestrians (no solution allowed inside agent's radius vs. increasing penalty [current])
Ideas on how to proceed:
- We implement the Nelder Mead on our own (it is after all a very easy algorithm), now
NELDER_MEAD_CIRCLE. Then we understand it better and have more control of constrains handling and other issues. @BZoennchen
- We analyze the behaviour of original Nelder Mead implementation. @hm-mayr9
- Design reference scenarios where we measure the error of the current Nelder Mead, so we have a way to see improvements. Done in !65 (merged)