Resolving configuration conflicts using a multi-valued decision diagram

• US 10,318,701 B2
• Filed: 10/14/2016
• Issued: 06/11/2019
• Est. Priority Date: 01/19/2016
• Status: Active Grant

• Current Assignee: Ford Motor Company
• Original Assignee: Ford Motor Company
• Inventors: Goodman, Bryan Roger, Hunsaker, Melinda Kaye, Newton, David Mark, Liu, Yu-Ning, Sabbagh, Essam Mahmoud, Sprague, Rickie Allan, Fradkin, Yakov M.
• Primary Examiner(s): Thangavelu, Kandasamy
• Application Number:
  US15/294,149
• Publication Number:
  US 20170206304A1
• Time in Patent Office: 970 Days
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 30/15 Vehicle, aircraft or watercraft design
• CPC Class Codes: G06Q 30/0621 Item configuration or customization

Abstract

A system is provided with a memory device and a processor. The memory device is adapted to store data representative of a multi-valued decision diagram (MDD) specifying a buildable space of all possible configurations of a vehicle. The processor is in communication with the memory and is programmed to identify an invalid configuration, and to generate a restricted buildable space, including to determine an edit distance of each complete path indicative of a number of features to change the invalid configuration of that path to one of the valid configurations, identify a minimum of the edit distances, and remove configurations having edit distances larger than the minimum. The processor is further programmed to identify at least one feature to change the invalid configuration to at least one valid configuration based on the restricted buildable space; and to generate output indicative of the at least one feature to change.

Claims

1. A system comprising:

a memory device adapted to store data representative of a multi-valued decision diagram (MDD) specifying a buildable space of all possible configurations of a vehicle, the MDD including a root node, a truth node, and at least one level of intervening nodes, each level of the MDD corresponding to a family of mutually-exclusive features represented by at least one node, each intervening node of a level connecting to nodes of a next adjacent level by outgoing edges having labels indicating valid features of the family and to nodes of a prior adjacent level by incoming edges that are outgoing edges of the prior adjacent level, such that a complete path from the root node through the outgoing edges to the truth node defines at least one of the valid configurations; and

a processor in communication with the memory, programmed to

identify an invalid configuration,

generate a restricted buildable space, including to

determine an edit distance of each complete path indicative of a number of features to change the invalid configuration of that path to one of the valid configurations,

identify a minimum of the edit distances, and

remove configurations having edit distances larger than the minimum; and

identify at least one feature to change the invalid configuration to at least one valid configuration based on the restricted buildable space; and

generate output indicative of the at least one feature to change.

2. The system of claim 1, wherein the processor is further programmed to provide a message to a user indicative of the at least one feature to change.

3. The system of claim 1, wherein the processor is further programmed to:

receive input indicative of a non-guided resolution; and

generate a further restricted buildable space having a single target configuration, including to

determine a weight of each path in the restricted buildable space, indicative of a priority of its features,

identify the maximum weight of all paths, and

remove configurations having weights that are less than the maximum weight.

4. The system of claim 3, wherein each feature is assigned a weight such that each path is uniquely weighted.

5. The system of claim 1, wherein the processor is further programmed to:

receive input indicative of a non-guided resolution; and

generate a further restricted buildable space having a single target configuration, including to

determine a number of standard features of each path in the restricted buildable space,

identify a maximum standard number of features of all paths, and

remove configurations having less than the maximum standard number of features.

6. The system of claim 1, wherein the processor is further programmed to:

receive input indicative of a non-guided resolution;

determine a first configuration corresponding to one of the valid configurations;

determine a second configuration corresponding to the invalid configuration in response to receiving a selection of at least one feature;

determine a first feature state for each feature of the first configuration, including at least one of Selected, Included and Default feature states;

generate a further restricted buildable space having a single target configuration, including to

determine a second feature state for each feature of the second configuration, including at least one of Selected, Included and Default feature states;

identify additions in the second configuration indicative of features present in the second configuration and not present in the first configuration, and the corresponding second feature state of each feature; and

identify subtractions in the second configuration indicative of features present in the first configuration and not present in the second configuration, and the corresponding first feature state of each feature.

7. The system of claim 6, wherein the processor is further programmed to:

receive a return delta indicative of an amount of information provided to a user in response to an invalid configuration; and

provide a message to the user indicative of the at least one feature to change to at least one valid configuration based on the further restricted buildable space and the return delta.

8. The system of claim 7, wherein the message is further indicative of all additions and subtractions in response to a return delta of true;

and

wherein the message is further indicative of no additions or subtractions having Default feature states in response to a return delta of false.

9. The system of claim 7, wherein the message is further indicative of only additions having Included feature states and only subtractions having Selected feature states in response to a return delta of false.

10. The system of claim 1, wherein the processor is further programmed to:

receive input indicative of a guided resolution; and

generate a further restricted buildable space having at least one target configuration, including to

determine a node weight indicative of a weight of the node to the truth node along each path in the restricted buildable space, wherein a positive weight is assigned to each feature included in the configuration and a weight of zero is assigned to each feature that is not included in the configuration,

identify a maximum node weight of all paths, and

remove configurations having weights that are less than the maximum node weight, and thereby remove partial matches.

11. The system of claim 1, wherein the processor is further programmed to:

receive input indicative of a guided resolution;

determine a first configuration corresponding to one of the valid configurations;

determine a second configuration corresponding to the invalid configuration in response to receiving a second selection of at least one feature;

generate a further restricted buildable space having multiple target configurations, including to

determine a bitset of the second configuration,

determine a domain bitset of the restricted buildable space,

calculate a bitwise conjunction of the second configuration bitset and the restricted buildable space bitset, and

identify at least one family to change as a family having no active bits in the bitwise conjunction; and

provide a message to a user that displays the at least one feature to change from each family to change, to resolve the at least one feature.

12. The system of claim 11, wherein the processor is further programmed to:

determine a resolution object, including nested resolution objects, indicative of actions required to change the invalid configuration to one of the valid configurations in the restricted buildable space, wherein every family to change will have at least one action, and wherein there is more than one choice, including to

identify a branch family as any family that leads to a divergent choice and the choices for remaining families are unknown until the branch family choice is identified,

identify a no-branch family as any family that does not lead to divergent choices for remaining families, and

provide the message to the user that displays the features from the no-branch families and no more than one branch family, and prompt the user to select from the displayed features.

13. A method comprising:

storing, in a memory, data representative of a multi-valued decision diagram (MDD) specifying a buildable space of all possible configurations of a vehicle, the MDD including a root node, a truth node, and at least one level of intervening nodes, each level of the MDD corresponding to a family of mutually-exclusive features represented by at least one node, each intervening node of a level connecting to nodes of a next adjacent level by outgoing edges having labels indicating valid features of the family and to nodes of a prior adjacent level by incoming edges that are outgoing edges of the prior adjacent level, such that a complete path from the root node through the outgoing edges to the truth node defines at least one of the valid configurations;

receiving input indicative of a non-guided resolution;

identifying an invalid configuration;

generating a restricted buildable space, including

determining an edit distance of each complete path indicative of a number of features to change the invalid configuration of that path to one of the valid configurations,

identifying a minimum of the edit distances, and

removing configurations having edit distances larger than the minimum,

generating a further restricted buildable space having a single target configuration, including

determining a weight of each path in the restricted buildable space, indicative of a priority of its features,

identifying the maximum weight of all paths, and

removing configurations having weights that are less than the maximum weight;

identifying at least one feature to change the invalid configuration to at least one valid configuration based on the further restricted buildable space; and

generating output indicative of the at least one feature to change.

14. The method of claim 13, further comprising:

determining a first configuration corresponding to one of the invalid configurations;

determining a second configuration corresponding to the single target configuration;

determining a first feature state for each feature of the first configuration, including at least one of Selected, Included and Default feature states;

determining a second feature state for each feature of the second configuration, including at least one of Selected, Included and Default feature states;

identifying additions in the second configuration indicative of features present in the second configuration and not present in the first configuration, and the corresponding second feature state of each feature;

identifying subtractions in the second configuration indicative of features present in the first configuration and not present in the second configuration, and the corresponding first feature state of each feature;

receiving a return delta indicative of an amount of information provided to a user in response to an invalid configuration; and

providing a message to the user that displays the at least one feature to change from each family to change to resolve the at least one feature.

15. The method of claim 14, wherein the message is indicative of all additions and subtractions in response to a return delta of true;

and

wherein the message is further indicative of no additions or subtractions having Default feature states in response to a return delta of false.

16. The method of claim 14, wherein the message is indicative of only additions having Included feature states and only subtractions having Selected feature states in response to a return delta of false.

17. A method comprising:

storing, in a memory, data representative of a multi-valued decision diagram (MDD) specifying a buildable space of all possible configurations of a vehicle, the MDD including a root node, a truth node, and at least one level of intervening nodes, each level of the MDD corresponding to a family of mutually-exclusive features represented by at least one node, each intervening node of a level connecting to nodes of a next adjacent level by outgoing edges having labels indicating valid features of the family and to nodes of a prior adjacent level by incoming edges that are outgoing edges of the prior adjacent level, such that a complete path from the root node through the outgoing edges to the truth node defines at least one of the valid configurations;

receiving input indicative of a guided resolution;

identifying an invalid configuration;

generating a restricted buildable space having multiple target configurations, including

determining an edit distance of each complete path indicative of a number of features to change the invalid configuration of that path to one of the valid configurations,

identifying a minimum of the edit distances, and

removing configurations having edit distances larger than the minimum,

identifying at least one family to change, including

determining a bitset of the invalid configuration,

determining a domain bitset of the restricted bhuildable space,

calculating a bitwise conjunction of the invalid configuration bitset and the restricted buildable space bitset, and

identifying the at least one family to change as a family having no active bits in the bitwise conjunction; and

providing a message to a user that displays at least one feature to change from each family to change, to resolve the at least one feature.

18. The method of claim 17, further comprising:

determining a resolution object, including nested resolution objects, indicative of actions required to change the invalid configuration to one of the valid configurations in the restricted buildable space, wherein every family to change will have at least one action, and wherein there is more than one choice, including

identifying a branch family as any family that leads to a divergent choice and the choices for remaining families are unknown until the branch family choice is identified,

identifying a no-branch family as any family as any family that does not lead to divergent choices for remaining families, and

providing the message to the user that displays the features from the no-branch families and no more than one branch family, and prompt the user to select from the displayed features.

19. The method of claim 17, further comprising:

determining a node weight indicative of a weight of the node to the truth node along each path in the restricted buildable space, wherein a positive weight is assigned to each feature included in the configuration and a weight of zero is assigned to each feature that is not included in the configuration;

identifying a maximum node weight of all paths; and

removing configurations having weights that are less than the maximum node weight, and thereby remove partial matches.

20. The method of claim 17, further comprising receiving a user selection of a feature that resulted in the invalid configuration.