I’m using ScatteredInterpolation to approximate a higher-order value function as needed.
The interpolation works reasonably well for points that are in some sense “inside” prior points that I’ve used. My plan is to use LazySets to create a convex hull of existing interpolation points. Then when a new request comes in, I check to see if it’s interior to the convex hull. If it is not, I want to add it.
However, I think the best approach will not be to add the just-request point. Instead, I want to move some distance “away” from the hull, so that if the next call is epsilon in the same direction, it will be in the interior. I think the way to calculate the direction “away” is to find the nearest point in the hull, and then move some distance in the opposite direction.
Given a point in R^N, and a convex hull of R^N. Assume, the point is not in the hull. How do I find closes point that is in the hull. Some potential solutions:
I think this is isomorphic to point in the
minkowski_differencethat has the smallest norm. But I don’t see how to find the point with the smallest norm.
Sample 100 points from the convex hull and then use the smallest.
I also wonder if there’s a way to iterate through all violated constraints, moving in the direction of the a_vector.
Don’t worry about finding the closest point, just find the closest vertex, as if there’s more than one violation, the closet point is going to be a vertex.(This is false. See image at end of post. The Green Point violates 3 constraints, but the nearest point is the blue point which is not a vertex.)
3+4: check the number of violated constraints. If it’s 1, that constraint’s vector tells us the direction. If it’s 2 or more, just iterate over vertices.