- Number
- 20170176994
- Published
- 2017-06-22
- Filed
- 2015-12-21
- Assignee
- Disney Enterprises, Inc.
- Inventors
- YEDIDIA; Jonathan S., BENTO; Jose, DERBINSKY; Nate, MATHY; Charles
- CPC
- G05D1/0217; G06F17/11; G06N3/006; G06N5/02; G06N7/01
- Verdict
- Medium Notable software
- Source
- Google Patents · FreePatentsOnline
The keeper's note
A multi-agent path planning method that solves an optimization problem with cost functions and landmark constraints to route agents to a goal.
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 where the cost functions have a relationship with the variables and receiving a landmark indicating a point that an agent is to visit while moving, a cost being associated with ignoring the landmark. The method includes generating a first message for the cost functions for the corresponding variable based uponthe relationship and a second message for each of the variables for the 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 repeating steps (c), (d), and (e) until a consensus is formed between the first and second messages until the optimization solution is determined based upon the consensus.
Background
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows a device for generating an optimization solution according to an exemplary embodiment.
FIG. 2 shows a graphical model according to an exemplary embodiment.
FIG. 3A shows a graphical model as applied to a multi-agent trajectory planning problem according to an exemplary embodiment.
FIG. 3B shows input and output variables for each operator of the graphical model of FIG. 3A according to an exemplary embodiment.
FIG. 4 shows a method of generating an optimization solution according to an exemplary embodiment.
FIG. 5A shows a convergence graph from using the method of FIG. 4.
FIG. 5B shows a distribution graph from using the method of FIG. 4.DETAILED DESCRIPTION
The exemplary embodiments relate to a device and method for planning trajectories for multiple agents. The exemplary embodiments may be further understood with reference to the following description and the appended drawings, wherein like elements are referred to with the same reference numerals. The exemplary embodiments describe a method and device for generating an optimization solution. Specifically,the method and device utilize a message-passing version of the ADMM algorithm that is applicable to determining trajectories that may travel within a three-dimensional space. The message-passing algorithm includes a weighting system in which a message passed between nodes of a graphical model may include weights associated with
Claims
1. A method, comprising: (a) receiving an optimization problem in which a plurality of agents are to move from a first configuration to a second configuration, the optimization 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 optimization problem, each of the cost functions having a predetermined relationship with select ones of the variables; (b) receiving atleast one landmark, each landmark indicating at least one point that a selected one of the agents is to visit while moving from the first configuration to the second configuration, a further possible cost for the values of the variables in the optimization problem being generated when the selected agent ignores the landmark; (c) 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 optimization problem is solved, the first message having a respective first weight indicating a certainty of the first message; (d) 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 optimization problem is solved, the second message having a respective second weight indicating a certainty of the second message; (e) generating a disagreement variable for each corresponding pair of variables and cost functions measuring a disagreement value between the first and second beliefs;(f) repeating steps (c), (d), and (e) 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 (g) determining an optimization solution based upon the consensus.
11. A device, comprising: a processor coupled to a memory,wherein the processor is programmed to determine an optimization solution to an optimization problem by: (a) receiving the optimization problem in which a plurality of agents are to move from a first configuration to a second configuration, the optimization 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 optimization problem, each of the cost functions having a predetermined relationship with select ones of the variables; (b) receiving at least one landmark, each landmark indicating at least one point that a selected one of the agents is to visit while moving from the first configuration to the second configuration, a further possible cost for the values of the variables in the optimization problem being generated when the selected agent ignores the landmark; (c) 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 optimization problem is solved, the first message having a respective first weight indicating a certainty of the first message; (d) generating a second message for each of the variables for each corresponding cost function based upon the respective predetermined relationship, the second message indicatinga second belief that the corresponding variable has a second value when the optimization problem is solved, the second message having a respective second weight indicating a certainty of the second message; (e) generating a disagreement variable for each corresponding pair of variables and cost functions measuring a disagreement value between the first and second beliefs; (f) repeating steps (c), (d), and (e) 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 (g) determining the optimization solution based upon the consensus.
20. 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 an optimization problem in which a plurality of agents are to move from a first configuration to a second configuration,the optimization 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 optimization problem, each of the cost functions having a predetermined relationship with select ones of the variables; (b) receiving at least one landmark, each landmark indicating at least one point that a selected one of the agents is to visit while moving from the first configuration to the second configuration, a further possible cost for the values of the variables in the optimization problem being generated when the selected agent ignores the landmark; (c) 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 optimization problem is solved, the first message having a respective first weight indicating a certainty of the first message; (d) 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 secondvalue when the optimization problem is solved, the second message having a respective second weight indicating a certainty of the second message; (e) generating a disagreement variable for each corresponding pair of variables and cost functions measuring a disagreementvalue between the first and second beliefs; (f) repeating steps (c), (d), and (e) until aconsensus 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 (g) determining an optimization solution based upon the consensus.