Since specifying an appropriate target-position might well be tricky in many situations, the following approach based on 2D occupancy grid-maps may be worth considering. It is commonly referred to as "value iteration", and combined with gradient-descent/ascent, it gives a simple and fairly efficient (depending on implementation) path-planning algorithm. Due to its simplicity, it is well-known in mobile robotics, in particular for "simple robots" navigating in indoor environments. As implied above, this approach provides a means of finding a path away from a start-position without explicitly specifying a target-position as follows. Note that a target-position can optionally be specified, if available. Also, the approach/algorithm constitutes a breadth-first search, and is to some degree related to potential field methods with attracting and repelling forces.
In the binary case, the 2D occupancy grid-map is one for occupied grid-cells and zero elsewhere. Note that this occupancy-value can also be continuous in the range [0,1], I'll get back to that below. The value of a given grid-cell gi is V(gi).
The Basic Version
- Assuming that grid-cell g0 contains the start-position. Set V(g0)=0, and put g0 in a FIFO-queue.
- Take the next grid-cell gi from the queue.
- For all neighbors gj of gi:
- If gj is not occupied and has not been visited previously:
- V(gj) = V(gi)+1
- Mark gj as visited.
- Add gj to the FIFO-queue.
- If a given distance-threshold is not reached yet, continue with (2.), otherwise continue with (5.).
- The path is obtained by following the steepest gradient-ascent starting from g0.
Notes on Step 4.
- As given above, step (4.) requires to keep track of the maximum distance covered, which has been omitted in the above description for reasons of clarity/brevity.
- If a target-position is given, the iteration is stopped as soon as the target-position is reached, i.e. processed/visited as part of step (3.).
- It is, off course, also possible to simply process the whole grid-map, i.e. to continue until all (free) grid-cells have been processed/visited. The limiting factor is obviously the size of the grid-map in conjunction with its resolution.
Extensions and Further Comments
The update-equation V(gj) = V(gi)+1 leaves plenty of room to apply all kinds of additional heuristics by either down-scaling V(gj) or the additive component in order to reduce the value for certain path-options. Most, if not all, such modifications can nicely and generically be incorporated using a grid-map with continuous values from [0,1], which effectively constitutes a pre-processing step of the initial, binary grid-map. For example, adding a transition from 1 to 0 along obstacle boundaries, causes the "actor" to preferably stay clean of obstacles. Such a grid-map can, for example, be generated from the binary version by blurring, weighted dilation, or similar. Adding the threats and enemies as obstacles with large blurring radius, penalizes paths that come close to these. One can also use a diffusion-process on the overall grid-map like this:
V(gj) = ( 1/(N+1) ) × [ V(gj) + sum( V(gi) ) ]
where "sum" refers to the sum over all neighboring grid-cells. For example, instead of creating a binary map, the initial (integer) values could be proportional to the magnitude of the threats, and obstacles present "small" threats. After applying the diffusion-process, the grid-values should/must be scaled to [0,1], and cells occupied by obstacles, threats, and enemies should be set/forced to 1. Otherwise the scaling in the update-equation may not work as desired.
There are many variations on this general scheme/approach. Obstacles etc. could have small values, while free grid-cells have large values, which may require gradient-descent in the last step depending on the objective. In any case, the approach is, IMHO, surprisingly versatile, fairly easy to implement, and potentially rather fast (subject to grid-map-size/resolution). Finally, as with many path-planning algorithms that don't assume a specific target-position, there is the obvious risk of getting stuck in dead-ends. To some extent, it might be possible to apply dedicated post-processing steps before the last step to reduce this risk.
Here's another brief description with an illustration in Java-Script (?), though the illustration didn't work with my browser :(
Lots more detail on planning can be found in the following book. Value iteration is specifically discussed in Chapter 2, Section 2.3.1 Optimal Fixed-Length Plans.
Hope that helps, kind regards, Derik.