# US 2025/0155249 A1 · System and method for computing optimal path based on loop variables with post-processing applied

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0155249 A1
- Document ID: US20250155249A1
- Status: Published application
- Kind: A1
- Application number: 18/775,172
- Filed: 2024-07-17
- Published: 2025-05-15
- Earliest claimed: 2023-11-15
- Assignees: Korea Advanced Institute of Science and Technology
- Applicants: Korea Advanced Institute of Science and Technology
- Inventors: In Gwun Jang; Geunu Kim; Jeonghun Kim; Kitae Jang
- Web page: https://patentgrep.com/patent/US20250155249A1

## CPC

- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

A system for computing an optimal path includes an arithmetic unit. The arithmetic unit is configured to compute an objective moving path from one of a plurality of nodes to another one of the plurality of nodes. Each of a plurality of link variables corresponds to a path connecting any two adjacent nodes of the plurality of nodes. Each of the plurality of link variables has a value and a direction. Each of a plurality of loop variables corresponds to a closed path connecting at least any three nodes of the plurality of nodes. Each of the plurality of loop variables has a value and a direction. A reference path variable corresponds to any moving path and has a value and a direction. The arithmetic unit computes the plurality of link variables based on the reference path variable and the plurality of loop variables. The arithmetic unit uses the plurality link variables to compute a plurality of objective function values corresponding, respectively, to a plurality of moving paths. The arithmetic unit computes a moving path corresponding to a minimum objective function value, which is the smallest value among the plurality of objective function values, as the objective moving path.

## Claims

### Claim 1

A system for computing an optimal path, comprising an arithmetic unit configured to compute an objective moving path from one of a plurality of nodes to another one of the plurality of nodes,
wherein a plurality of link variables are defined, each of the plurality of link variables corresponding to a path connecting any two adjacent nodes of the plurality of nodes and having a value and a direction, wherein a plurality of loop variables are defined, each of the plurality of loop variables corresponding to a closed path connecting at least any three nodes of the plurality nodes and having a value and a direction, and wherein a reference path variable is defined, the reference path variable corresponding to any moving path and having a value and a direction,
wherein the arithmetic unit is configured to compute the plurality of link variables based on the reference path variable and the plurality of loop variables, compute a plurality of objective function values corresponding, respectively, to a plurality of moving paths using the plurality link variables, and compute a moving path corresponding to a minimum objective function value, which is the smallest value among the plurality of objective function values, as the objective moving path.

### Claim 2 (depends on 1)

The system for computing an optimal path as set forth in claim 1, wherein a first link variable of the plurality of link variables corresponds to a path connecting a first node and a second node of the plurality of nodes, and a first loop variable of the plurality of loop variables corresponds to a closed path connecting the first node, the second node and a third node of the plurality of nodes, and
wherein the arithmetic unit is configured to compute a value of the first link variable based on a result of comparing the direction of the first link variable with the direction of the first loop variable and with the direction of the reference path variable.

### Claim 3 (depends on 2)

The system for computing an optimal path as set forth in claim 2, wherein the arithmetic unit is configured to calculate a link variable median by adding the value of the first loop variable to a predetermined value when the direction of the first loop variable is the same as the direction of the first link variable and calculate the link variable median by subtracting the value of the first loop variable from the predetermined value when the direction of the first loop variable is different from the direction of the first link variable, and
wherein the arithmetic unit is configured to calculate the value of the first link variable by adding the value of the reference path variable to the link variable median when the direction of the reference path variable is the same as the direction of the first link variable and calculate the value of the first link variable by subtracting the value of the reference path variable from the link variable median when the direction of the first loop variable is different from the direction of the first link variable.

### Claim 4 (depends on 3)

The system for computing an optimal path as set forth in claim 3, wherein a plurality of cost variables are defined, each of the plurality of cost variables corresponding to a path connecting any two adjacent nodes of the plurality of nodes, and
wherein the arithmetic unit is configured to further use the plurality of cost variables to calculate the plurality of objective function values.

### Claim 5 (depends on 3)

The system for computing an optimal path as set forth in claim 3, wherein the arithmetic unit is configured to compute the plurality of objective function values using Equation 1, the Equation 1 being
Minimize
⁢
f
⁡
(
X
)
=
∑
i
=
1
∑
j
=
1
c
i
,
j
⁢
x
i
,
j
,
whereas f(X) corresponds to any one of the plurality of objective function values, i and j each corresponds to any one of the plurality of nodes, ci,j corresponds to any one of the plurality of cost variables, and xi,j corresponds to any one of the plurality of link variables.

### Claim 6 (depends on 3)

The system for computing an optimal path as set forth in claim 3, wherein the arithmetic unit is configured to perform at least one iteration in which at least some of the plurality of loop variables are changed such that the minimum objective function value is reduced.

### Claim 7 (depends on 6)

The system for computing an optimal path as set forth in claim 6, wherein the arithmetic unit is configured to change at least some of the plurality of loop variables using at least one of SQP (sequential quadratic programming), convex optimization, gradient-based methods, genetic algorithms, simulated annealing, interior-point methods and dynamic programming in the process of performing the iteration.

### Claim 8 (depends on 6)

The system for computing an optimal path as set forth in claim 6, wherein the arithmetic unit is configured to perform the iteration multiple times, and
wherein the arithmetic unit is configured to determine whether to terminate the iteration based on a rate at which the minimum objective function value is reduced through the iteration.

### Claim 9 (depends on 8)

The system for computing an optimal path as set forth in claim 8, wherein the arithmetic unit is configured to terminate the iteration if the rate at which the minimum objective function value is reduced is less than a predetermined iteration threshold ratio.

### Claim 10 (depends on 6)

The system for computing an optimal path as set forth in claim 6, wherein the arithmetic unit is configured to determine whether to terminate the iteration based on a value by which the minimum objective function value is reduced through the iteration.

### Claim 11 (depends on 6)

The system for computing an optimal path as set forth in claim 6, wherein the arithmetic unit is configured to perform the iteration for a predetermined number of iterations.

### Claim 12 (depends on 6)

The system for computing an optimal path as set forth in claim 6, wherein the arithmetic unit is configured to calculate a plurality of post-processing loop variables by changing, among the plurality of loop variables changed through the iteration, a value of a loop variable smaller than a post-processing threshold to 0 and compute a plurality of objective moving paths using the plurality of post-processing loop variables.

### Claim 13 (depends on 12)

The system for computing an optimal path as set forth in claim 12, wherein the arithmetic unit is configured to calculate a plurality of post-processing loop variables and a plurality of objective moving paths corresponding, respectively, to a plurality of post-processing thresholds.

### Claim 14

A method for computing an optimal path using an arithmetic unit configured to compute an objective moving path from one of a plurality of nodes to another one of the plurality of nodes, the method comprising:
defining a basic variable, in which the arithmetic unit defines a plurality of link variables, each of the plurality of link variables corresponding to a path connecting any two adjacent nodes of the plurality of nodes and having a value and a direction, defines a plurality of loop variables, each of the plurality of loop variables corresponding to a closed path connecting any three nodes of the plurality of nodes and having a value and a direction, and defines a reference path variable corresponding to any moving path and having a value and a direction;
calculating a link variable, in which the arithmetic unit calculates a plurality of link variables based on the reference link variable and the plurality of loop variables;
calculating an objective function, in which the arithmetic unit calculates a plurality of objective function values, each of the plurality of objective function values corresponding to a plurality of moving paths, using the plurality of link variables; and
calculating an optimal path, in which the arithmetic unit calculates a moving path corresponding to a minimum objective function value, which is the smallest value among the plurality of objective function values, as the objective moving path.

### Claim 15 (depends on 14)

The method for computing an optimal path as set forth in claim 14, wherein the step of calculating the link variable includes calculating a first link variable and calculating a second link variable,
wherein, in the step of calculating the first link variable, the arithmetic unit calculates a link variable median by adding the value of a first loop variable to a predetermined value when the direction of the first loop variable is the same as the direction of the first link variable and calculates the link variable median by subtracting the value of the first loop variable from the predetermined value when the direction of the first loop variable is different from the direction of the first link variable, and
wherein, in the step of calculating the second link variable, the arithmetic unit calculates the value of the first link variable by adding the value of the reference path variable to the link variable median when the direction of the reference path variable is the same as the direction of the first link variable and calculates the value of the first link variable by subtracting the value of the reference path variable from the link variable median when the direction of the first loop variable is different from the direction of the first link variable.

### Claim 16 (depends on 14)

The method for computing an optimal path as set forth in claim 14, wherein, in the step of calculating the objective function, the arithmetic unit defines a plurality of cost variables, each of the plurality of cost variables corresponding to a path connecting any two adjacent nodes of the plurality of nodes, and further uses the plurality of cost variables to calculate the plurality of objective function values.

### Claim 17 (depends on 14)

The method for computing an optimal path as set forth in claim 14, wherein, in the step of calculating the objective function, the arithmetic unit calculates the plurality of objective function values using Equation 1, the Equation 1 being
Minimize
⁢
f
⁡
(
X
)
=
∑
i
=
1
∑
j
=
1
c
i
,
j
⁢
x
i
,
j
,
whereas f(X) corresponds to any one of the plurality of objective function values, i and j each corresponds to any one of the plurality of nodes, ci,j corresponds to any one of the plurality of cost variables, and xi,j, corresponds to any one of the plurality of link variables.

### Claim 18 (depends on 17)

The method for computing an optimal path as set forth in claim 17, further comprising performing an iteration operation,
wherein, in the step of performing the iteration operation, the arithmetic unit performs at least one iteration in which at least some of the plurality of loop variables are changed such that the minimum objective function value is reduced.

### Claim 19 (depends on 18)

The method for computing an optimal path as set forth in claim 18, wherein, in the step of performing the iteration operation, the arithmetic unit determines whether to terminate the iteration based on a rate at which the minimum objective function value is reduced through the iteration or based on a value by which the minimum objective function value is reduced through the iteration.

### Claim 20 (depends on 18)

The method for computing an optimal path as set forth in claim 18, further comprising performing a post-process,
wherein the arithmetic unit calculates a plurality of post-processing loop variables by changing, among the plurality of loop variables changed through the iteration, a value of a loop variable smaller than the post-processing threshold to 0.