# US 2019/0244111 A1 · Avoiding dead ends in real-time heuristic search > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0244111 A1 - Document ID: US20190244111A1 - Status: Published application - Kind: A1 - Application number: 16/266,806 - Filed: 2019-02-04 - Published: 2019-08-08 - Earliest claimed: 2018-02-02 - Assignees: University of New Hampshire - Applicants: University of New Hampshire - Inventors: Wheeler Ruml; Bence Cserna; William Doyle; Jordan Ramsdell - Web page: https://patentgrep.com/patent/US20190244111A1 ## CPC - G06N 3/008: based on physical entities controlled by simulated intelligence so as to replicate intelligent life forms, e.g. based on robots replicating pets or humans in their appearance or behaviour - G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound - G06N 5/04: Inference or reasoning models - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract A system that avoids dead-end states during a real-time heuristic search. While transitioning from a previous state to a current state, the system may perform lookahead to populate a state-space with potential states. The system may identify safe states using a safety predicate and only select potential states that are ancestors of safe states, providing a clear path to safety when needed. In addition, the system may determine a distance-to-safety function that indicates a number of state transitions between each potential state and a nearest safe state. ## Claims ### Claim 1 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 that a first state of the plurality of potential states is a safe state, wherein the safe state is likely to reach at least one of a plurality of goal states; determining that a second state of the plurality of potential states is an ancestor to the first state in the state space; determining a first cost value that indicates an estimated cost to reach the goal state from the second state; selecting the second state based at least in part on the first cost value; and performing an action to transition from the current state towards the second state. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, further comprising: performing state expansion on the plurality of potential states using a first ratio, the first ratio dividing processing time between expanding states based on a cost function and expanding states based on a safety function, wherein the first cost value corresponds to the cost function, and the safety function is used to determine that the first state is likely to reach at least one of the plurality of goal states. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, further comprising: determining a first portion of the plurality of potential states that corresponds to one or more safe states, wherein each potential state of the one or more safe states is likely to reach at least one of the plurality of goal states, the first portion including the first state; determining a second portion of the plurality of potential states that corresponds to one or more comfortable states, wherein each potential state of the second portion has at least one descendant state included in the first portion, the second portion including the second state; determining cost values associated with at least some of the second portion; and determining that the first cost value is lowest of the cost values. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, further comprising: determining a first portion of the plurality of potential states that corresponds to one or more safe states, the first portion including the first state; determining safety values associated with a second portion of the plurality of potential states, wherein the safety values indicate a number of state transitions between each potential state of the second portion and a nearest potential state of the first portion; and selecting a subset of the second portion based on a threshold value, wherein the safety values associated with the subset are below the threshold value. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, further comprising: determining that the second state is two or more state transitions away from the current state; determining that a third state of the plurality of potential states is an ancestor to the second state; performing a second action to transition from the current state to the third state; and performing the action to transition from the third state towards the second state. ### Claim 6 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. ### Claim 7 (depends on 6) The computer-implemented method of claim 6, further comprising: performing state expansion on the plurality of potential states using a first ratio, the first ratio dividing processing time between expanding states based on a cost function and expanding states based on a safety function, wherein the cost values correspond to the cost function, and the safety function is used to identify the one or more safe states. ### Claim 8 (depends on 6) The computer-implemented method of claim 6, further comprising: determining safety values associated with the second portion, wherein the safety values indicate a number of state transitions between each potential state and one of the one or more safe states; and selecting a subset of the second portion based on a threshold value, wherein the safety values associated with the subset are below the threshold value. ### Claim 9 (depends on 6) The computer-implemented method of claim 6, further comprising: determining that the first state is two or more state transitions away from the current state; determining that a second state of the plurality of potential states is an ancestor to the first state; performing a second action to transition from the current state to the second state; and performing the action to transition from the second state towards the first state. ### Claim 10 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. ### Claim 11 (depends on 10) The computer-implemented method of claim 10, further comprising: performing state expansion on the plurality of potential states using a first ratio, the first ratio dividing processing time between expanding states based on a cost function and expanding states based on a safety function, wherein the cost values correspond to the cost function and the safety function is used to identify the plurality of safe sates. ### Claim 12 (depends on 10) The computer-implemented method of claim 10, further comprising: determining a second portion of the plurality of potential states that corresponds to one or more safe states, the second portion including the second state; determining the first portion, wherein each potential state of the first portion has at least one descendant state included in the second portion. ### Claim 13 (depends on 10) The computer-implemented method of claim 10, further comprising: determining safety values associated with the plurality of potential states, wherein the safety values indicate a number of state transitions between each potential state and one of the plurality of safe states; and selecting the first portion based on a threshold value, wherein the safety values associated with the first portion are below the threshold value. ### Claim 14 (depends on 10) The computer-implemented method of claim 10, further comprising: determining that the second state is two or more state transitions away from the current state; determining that a third state of the plurality of potential states is an ancestor to the second state; performing a second action to transition from the current state to the third state; and performing the action to transition from the third state towards the second state. ### Claim 15 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. ### Claim 16 (depends on 15) The computer-implemented method of claim 15, further comprising: identifying, during the first state expansion, a first portion of the plurality of potential states; determining that no potential state of the first portion has a descendant state that is likely to reach one of the plurality of goal states; and performing second state expansion using a second ratio, wherein the second ratio increases the processing time associated with expanding states based on the safety function. ### Claim 17 (depends on 15) The computer-implemented method of claim 15, further comprising: identifying, during the first state expansion, a first portion of the plurality of potential states; determining that at least one potential state of the first portion has a descendant state that is likely to reach one of the plurality of goal states; and performing second state expansion using a second ratio, wherein the second ratio increases the processing time associated with expanding states based on the cost function. ### Claim 18 (depends on 15) The computer-implemented method of claim 15, further comprising: determining a first portion of the plurality of potential states that corresponds to one or more safe states, the first portion including a second state of the plurality of potential states; and 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. ### Claim 19 (depends on 15) The computer-implemented method of claim 15, further comprising: determining safety values associated with the plurality of potential states, wherein the safety values are determined using a safety function and indicate a number of state transitions between each potential state and one of a plurality of safe states; and selecting a first portion of the potential states based on a threshold value, wherein safety values associated with the first portion are below the threshold value. ### Claim 20 (depends on 15) The computer-implemented method of claim 15, further comprising: determining that the first state is two or more state transitions away from the current state; determining that a second state of the plurality of potential states is an ancestor to the first state; performing a second action to transition from the current state to the second state; and performing the action to transition from the second state towards the first state. ### Claim 21 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.