Avoiding dead ends in real-time heuristic search

A computer-implemented method comprising:

• determining a current state in a state space;
• determining a plurality of potential states in the state space, wherein the current state is an ancestor to the plurality of potential states;
• determining a first portion of the plurality of potential states that correspond to one or more safe states, wherein each of the one or more safe states is likely to reach at least one of a plurality of goal states;
• determining that each potential state of a second portion of the plurality of potential states has at least one descendant state that is included in the first portion, the second portion including a first state of the plurality of potential states;
• determining cost values associated with the second portion, wherein a first cost value indicates an estimated cost to reach one of the plurality of goal states from the first state;
• determining that the first cost value is lowest of the cost values;
• and
• performing an action to transition from the current state towards the first state.

A computer-implemented method comprising:

• determining a current state in a state space;
• determining a plurality of potential states in the state space, wherein the current state is an ancestor to the plurality of potential states and the plurality of potential states includes a first state and a second state;
• determining cost values associated with a first portion of the plurality of potential states, wherein the first portion includes the first state and a first cost value indicates an estimated cost to reach one of a plurality of goal states from the first state;
• determining that the first cost value is lowest of the cost values;
• determining that the second state is one of a plurality of safe states, wherein each of the plurality of safe states is likely to reach one of the plurality of goal states;
• determining that the second state is an ancestor to the first state in the state space;
• and
• performing an action to transition from the current state towards the second state.

A computer-implemented method comprising:

• determining a current state in a state space;
• determining a plurality of potential states in the state space, wherein the current state is an ancestor to the plurality of potential states and the plurality of potential states includes a first state;
• performing first state expansion using a first ratio, the first ratio dividing processing time between expanding potential states based on a cost function and expanding potential states based on a safety function, wherein the cost function is used to determine a first cost value indicating an estimated cost to reach one of a plurality of goal states from the first state, and the safety function is used to determine that at least one descendant of the first state is a safe state that is likely to reach one of the plurality of goal states;
• selecting, based on the first cost value, the first state;
• and
• performing an action to transition from the current state towards the first state.

A computer-implemented method comprising:

• determining a current state in a state space;
• determining that a first potential state is a descendant of the current state;
• determining, based on a goal predicate, that the first potential state does not correspond to one of a plurality of goal states;
• determining, based on a safety predicate, that the first potential state corresponds to one of a plurality of safe states, wherein each of the plurality of safe states is likely to reach one of the plurality of goal states;
• determining a first cost value corresponding to the first potential state, the first cost value indicating an estimated cost to reach one of the plurality of goal states from the first potential state;
• selecting the first potential state based on the first cost value and the first potential state corresponding to one of the plurality of safe states;
• and
• performing an action to transition from the current state towards the first potential state.