Problem 611956 · medium · Robotics · Level 06 Estimation and Autonomy

Stuck in Front of the Pillar

potential field · gradient descent · local minimum · simulation · stopping rules

A museum robot glides toward its goal by following a potential field. At a point (x, y) (metres) the force on it is the pull of the goal plus the push of every pillar:

  • the pull is k_{att}\,(\text{goal} - p);
  • a pillar (ox, oy, r) is a disc. With \rho the distance from the robot to its centre and d = \rho - r the distance to its surface, it pushes only if d < d_0, straight away from its centre, with magnitude k_{rep}\,(1/d - 1/d_0)/d^2.

gains = (k_att, k_rep, d0). The robot visits positions $p_0 = $ start, p_1, p_2, \dots At each position p_k, in this order:

  1. If p_k is within 0.1 m of the goal (distance <= 0.1): stop with outcome "goal".
  2. Compute the force F at p_k. If its length |F| < 0.01: stop with "stuck" (the forces cancel: a local minimum or a balance point).
  3. If k == max_iter: stop with "moving" (the step budget is used up).
  4. The step is 0.05\,F, but if that is longer than 0.2 m, shrink it (same direction) to exactly 0.2 m. p_{k+1} = p_k + \text{step}.
  5. If p_{k+1} lies inside or on a pillar (\rho \le r for some pillar): stop at once with "crash" and k + 1.

Write field_descent(start, goal, obstacles, gains, max_iter) that returns (outcome, k, (x, y)): the outcome, the index of the position where the robot stopped, and that position. Collect the positions and press Run with plot(xs, ys) to see the trap.

Examples

Input:  start = (0, 0), goal = (10, 0), obstacles = [(5, 0, 1)], gains = (1, 5, 3), max_iter = 500
Output: ("stuck", 20, (3.1878127982502202, 0.0))
Explanation: the pillar stands right on the line to the goal. Everything stays on the
x axis, and the robot settles where the push balances the pull.

Input:  start = (0, 0.3), goal = (10, 0), obstacles = [(5, 0, 1)], gains = (1, 5, 3), max_iter = 500
Output: ("goal", 118, (9.917426623047177, 0.053279326651800255))
Explanation: starting a little off the line, the push has a sideways part and the robot
slides round the pillar.

Input:  start = (0, 0), goal = (6, 2), obstacles = [], gains = (1, 5, 3), max_iter = 10
Output: ("moving", 10, (1.897366596101028, 0.632455532033676))
Explanation: ten capped steps of 0.2 m along (6, 2), and the budget is used up.

Constraints

  • start lies outside every pillar; answers are compared with a tolerance of 1e-6

Goals

  • Follow a potential field step by step with a capped step length
  • Recognise a local minimum: the forces cancel before the goal is reached
  • Apply several stopping rules in a stated order
Starting Python…