Find minimum number of steps to a goal without estimator for how close intermediate steps are to the goal

Question

I've been trying to find a good way of solving the following problem, but I'm not sure how to even frame it. I think there might be relatively well-known solutions I'm not familiar with, since I don't have much knowledge of algorithms. How could I approach this?

Example problem:

There's a known begin-state A and known end-state B. There is a known sequence of (a large amount of) points that lead from A to B. I would like to find a minimum/small number of points that will describe the path from A to B. I can test for any sequence of points whether it reaches B using that, but if it doesn't I don't have an estimation of how close it is to getting to B. I'm basically trying to find the points that are essential for getting to B, but I won't know whether they are sufficient until the path is complete.

What I found so far:

The problem appears a bit similar to polyline simplification, and one option would be the Ramer Douglas Peucker algorithm. I don't think it will work well for my problem though, because I don't necessarily want to follow the non-essential points on the path(which may be outliers or unnecessary circumventions).

The solution I came up with myself sounds a bit like greedy & binary search:

1. Pick middle point C between A and B and discard all points between A and C.
2. Check whether this path reaches B.
3. If B cannot be reached, there is an essential point between A and C we missed, so pick middle point D between A and C and test path with points between A and D discarded.
   If B can be reached, we might be able to discard point C and some subsequent points, so pick D between C and B and discard points until D.
4. Do this until identified a point D furthest from A that still leads to B if all the points between A and D are discarded.
5. Start this search over, now starting from D instead of A until all essential points have been identified

Other thoughts:

I might be able to give a "similarity" estimation for end-state B1 that is reached from some point C in comparison to the targeted end-state B. Would that provide a wider variety of applicable algorithms?

Answer 1

Your problem sounds like in can be described in terms of finding the shortest path between two points on a graph; if you are able to rephrase it in those terms, Dijkstra's algorithm is probably what you're looking for.

You say you have no way of estimating the path length, but if you can provide a lower bound on it that varies to some degree you may be able to reduce the amount of effort required to perform your search using A* search.

Answer 2

Initially you have n steps going from A to B. Now you construct a vector p containing n 0s or 1s where the i-th 0 indicates that the i-th step is left out and a 1 indicates the step is done.

You want to find a p with minimal norm (sum of elements) under the condition that function f(p)=1.

f(p) is defined as 1 if the path containing of the steps where p is 1 is getting you from A to B. Function f is given by you. Either it is only 1 and 0 (path doesn't reach B) or you may also have a similarity estimate (how close the path reaches to B) which corresponds to f taking for example all possible values between 0 and 1 where close to 1 means "almost reaching B".

Now, you did not specify further knowledge about f. Does it have many local optima or is it continuous (if it is the similarity measure)?

If nothing is known about f I guess the only choice is starting with p of minimal norm and working its way upwards (so only one step, then all combinations of only two steps, ...) until you hit the first time a solution and stop. This might end up in NP running time.

If f is continuous this kind of reminds me on Langrange multipliers which might be used for minimizing the norm of p while keeping the path described by p a solution.