- Number
- 10572807
- Published
- 2020-02-25
- Filed
- 2016-03-31
- Assignee
- Disney Enterprises, Inc.
- Inventors
- Yedidia; Jonathan, Derbinsky; Nate, Pereira; Jose Bento Ayres, Schmidt; Dan, Mathy; Charles
- CPC
- G06Q10/04; G06N5/04
- Verdict
- Set aside generic optimization algorithm, business
- Source
- Google Patents · FreePatentsOnline
Abstract
A method and device determines an optimization solution for an optimization problem. The method includes receiving the optimization problem having cost functions and variables in which each of the cost functions has a predetermined relationship with select ones of the variables. The variables comprise a sub-solution of a spline indicative of a curved path along an estimated trajectory. The method includes generating a first message for each of the cost functions for each corresponding variable based upon the relationship and a second message for each of the variables for each corresponding cost function based upon the relationship. The method includes generating a disagreement variable for each corresponding pair of variables and cost functions measuring a disagreement value between the first and second beliefs. The method includes forming a consensus between the first and second messages until the optimization solution is determined.
Background
BACKGROUND INFORMATION(1) An optimization algorithm may be used to determine a solution for a problem in which the solution considers all variables and constraints related to the problem and provides a lowest cost configuration of the values for all the variables. For example, in a televised event, a plurality of cameras may be used to capture the event. The cameras may move along planned trajectories to fully capture the event. Accordingly, the problem associated with such a scenario may be to determine the planned trajectories for the cameras that incorporate the variables and constraints associated therewith. Such variables and constraints may include no overlap of space as the cameras cannot physically be co-located at a common time, a trajectory path that provides a sufficient video capture of the event, a tracking algorithm for the occurrences during the event, etc. Through incorporation of all these considerations, the optimization algorithm may determine the trajectories of the cameras to provide the lowest cost solution (e.g., least distance to be covered by the cameras, best coverage of the event, least energy requirements, etc.). However, most optimization algorithms require significantly high processing requirements for all these considerations to be assessed as well as provide the lowest cost solution to the problem.(2) A conventional algorithm used for convex optimization is the Alternating Direction Method of Multipliers (ADMM). Conventionally, the ADMM algorit
Claims
1. A method, comprising: (a) receiving a trajectory planning problem in which a plurality of agents move from a first configuration to a second configuration, the trajectory planning problem including a plurality of cost functions and a plurality of variables, the cost functions representing possible costs for values of the variables in the trajectory planning problem, each of the cost functions having a predetermined relationship with select ones of the variables, wherein the variables comprise at least one sub-solution to at least one sub-problem associated with the trajectory planning problem, the sub-solution being a spline indicative of a curved path along an estimated trajectory; (b) generating a first message for each of the cost functions for each corresponding variable based upon the respective predetermined relationship, the first message indicating a first belief that the corresponding variable has a first value when the trajectory planning problem is solved, the first message having a respective first weight indicating a certainty of the first message; (c) generating a second message for each of the variables for each corresponding cost function based upon the respective predetermined relationship, the second message indicating a second belief that the corresponding variable has a second value when the trajectory planning problem is solved, the second message having a respective second weight indicating a certainty of the second message; (d) generating a disagreement variable for each corresponding pair of variables and cost functions measuring a disagreement value between the first and second beliefs; (e) repeating steps (b), (c), and (d) until a consensus is formed between the first and second messages, a subsequent first message being modified based upon the second message, its corresponding second weight, and the corresponding disagreement variable, and a subsequent second message being modified based upon the first message, its corresponding first weight, and the corresponding disagreement variable; (f) determining a trajectory planning solution based upon the consensus, wherein the plurality of agents are configured to be moved from the first configuration to the second configuration based upon the trajectory planning solution.
10. A device, comprising: a processor coupled to a memory, wherein the processor is programmed to determine a trajectory planning solution to a trajectory planning problem by: (a) receiving the trajectory planning problem in which a plurality of agents move from a first configuration to a second configuration, the trajectory planning problem including a plurality of cost functions and a plurality of variables, the cost functions representing possible costs for values of the variables in the trajectory planning problem, each of the cost functions having a predetermined relationship with select ones of the variables, wherein the variables comprise at least one sub-solution to at least one sub-problem associated with the optimization problem, the sub-solution being a spline indicative of a curved path along an estimated trajectory; (b) generating a first message for each of the cost functions for each corresponding variable based upon the respective predetermined relationship, the first message indicating a first belief that the corresponding variable has a first value when the trajectory planning problem is solved, the first message having a respective first weight indicating a certainty of the first message; (c) generating a second message for each of the variables for each corresponding cost function based upon the respective predetermined relationship, the second message indicating a second belief that the corresponding variable has a second value when the trajectory planning problem is solved, the second message having a respective second weight indicating a certainty of the second message; (d) generating a disagreement variable for each corresponding pair of variables and cost functions measuring a disagreement value between the first and second beliefs; (e) repeating steps (b), (c), and (d) until a consensus is formed between the first and second messages, a subsequent first message being modified based upon the second message, its corresponding second weight, and the corresponding disagreement variable, and a subsequent second message being modified based upon the first message, its corresponding first weight, and the corresponding disagreement variable; and (f) determining the trajectory planning solution based upon the consensus, wherein the plurality of agents are configured to be moved from the first configuration to the second configuration based upon the trajectory planning solution.
18. A non-transitory computer readable storage medium with an executable program stored thereon, wherein the program instructs a microprocessor to perform operations comprising: (a) receiving a trajectory planning problem in which a plurality of agents move from a first configuration to a second configuration, the trajectory planning problem including a plurality of cost functions and a plurality of variables, the cost functions representing possible costs for values of the variables in the trajectory planning problem, each of the cost functions having a predetermined relationship with select ones of the variables, wherein the variables comprise at least one sub-solution to at least one sub-problem associated with the trajectory planning problem, the sub-solution being a spline indicative of a curved path along an estimated trajectory; (b) generating a first message for each of the cost functions for each corresponding variable based upon the respective predetermined relationship, the first message indicating a first belief that the corresponding variables has a first value when the trajectory planning problem is solved, the first message having a respective first weight indicating a certainty of the first message; (c) generating a second message for each of the variables for each corresponding cost function based upon the respective predetermined relationship, the second message indicating a second belief that the corresponding variable has a second value when the trajectory planning problem is solved, the second message having a respective second weight indicating a certainty of the second message; (d) generating a disagreement variable for each corresponding pair of variables and cost functions measuring a disagreement value between the first and second beliefs; (e) repeating steps (b), (c), and (d) until a consensus is formed between the first and second messages, a subsequent first message being modified based upon the second message, its corresponding second weight, and the corresponding disagreement variable, and a subsequent second message being modified based upon the first message, its corresponding first weight, and the corresponding disagreement variable; and (f) determining a trajectory planning solution based upon the consensus, wherein the plurality of agents are configured to be moved from the first configuration to the second configuration based upon the trajectory planning solution.