Maximally standard automatic completion using a multi-valued decision diagram

• US 10,318,703 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: Hunsaker, Melinda Kaye, Goodman, Bryan Roger, Fradkin, Yakov M.
• Primary Examiner(s): Thangavelu, Kandasamy
• Application Number:
  US15/294,395
• Publication Number:
  US 20170206305A1
• 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 adapted to store at least one multi-valued decision diagram (MDD) that specifies a total buildable space and a processor that is programmed to identify a partial configuration; generate a restricted buildable space of the total buildable space; and identify families to complete. The processor is further programmed to, for each family to complete in priority order, add any available standard features for the family to a possible set, if the possible set is empty, add a domain space of the family to the possible set, select the highest priority feature of the possible set as a Default feature state, and generate a further restricted buildable space of the total buildable space based on the Default feature state. The processor is also further programmed to generate a complete configuration including features having Default feature states for each family to complete.

Claims

1. 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;

identifying a minimally complete configuration including features having Selected and Included feature states;

generating a restricted buildable space of the MDD based on the minimally complete configuration;

generating a further restricted buildable space of the MDD including features having Default feature states, including

identifying families that do not include features with Selected or Included feature states as families to change,

determining a weight of each path in the restricted buildable space, indicative of a priority of the features along the path based on predetermined data,

identifying the maximum weight of all paths,

removing configurations having weights that are less than the maximum weight, and

for each family to change along the maximum weight path, set the highest priority feature to the Default feature state;

wherein each family along the maximum weight path includes a feature having a Selected, Included or Default feature state to generate a complete configuration.

2. The method of claim 1, wherein the restricted buildable space is generated during a downward traversal of the MDD and the path weights are calculated on an upward traversal of the MDD.

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

4. The method of claim 3 wherein the weight of each path is represented by a bitset indicative of a sum of the weight of each feature along the path.

5. The method of claim 4, wherein identifying the maximum weight of all paths further comprises sorting the bitset for each path in descending order.

6. The method of claim 1, wherein the weight of each feature is defined by an alternate structure separate from the MDD.

7. 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;

identifying a minimally complete configuration including features having Selected and Included feature states;

generating a restricted buildable space of the MDD based on the minimally complete configuration;

identifying families that do not include features with Selected or Included feature states as families to complete;

sorting the families to complete by a predefined family priority order;

for each family to complete in priority order,

if the family has a standard feature available in the restricted buildable space, setting the standard feature to a Default feature state, otherwise setting a highest priority available feature to the Default feature state, and

generating a further restricted buildable space of the MDD based on the Default feature; and

identifying a complete configuration once each family to complete is assigned a Default feature.

8. The method of claim 7, further comprising setting a highest priority standard feature to a Default feature state for each family to complete having more than one standard feature.

9. The method of claim 7, further comprising determining an availability of each feature from predetermined feature conditions indicative of relationships between the families, including:

(i) standard for a feature that is included in a base vehicle; and

(ii) optional for a feature that is not included in the base vehicle.

10. A system comprising:

a memory device adapted to store data representative of at least one multi-valued decision diagram (MDD) specifying a total buildable space of all possible configurations of a vehicle, each MDD including a root node, a truth node, and at least one level of intervening nodes, each level of each 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 a partial configuration including features having Selected and Included feature states;

generate a restricted buildable space of the total buildable space based on the partial configuration;

identify families that do not include features with Selected or Included feature states as families to complete;

for each family to complete in priority order,

add any available standard features for the family to a possible set,

if the possible set is empty, add a domain space of the family to the possible set,

set the highest priority feature of the possible set to a Default feature state according to an alternate sequence indicative of priority of the features, and

generate a further restricted buildable space of the total buildable space based on the Default feature; and

generate a complete configuration including features having Default feature states for each family to complete.

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

initialize the possible set to an empty set; and

for each feature,

find a list of essential sets for the feature, and

if an intersection of all spaces in the essential set is not empty, add the feature to the possible set;

wherein the intersection is empty if the feature is not standard or the feature is not currently available with the partial configuration.

12. The system of claim 11, wherein, to find the list of essential sets for the feature, the processor is further programmed to:

initialize a setlist to the restricted buildable space;

if a relationships work object is non-trivial, add the relationships work object to the setlist, wherein the relationship works object defines a temporary object that is used to process specific relationship conditions between families based on an order the families are processed;

if a standard space for the feature is not empty, add the standard space to the setlist;

if the family is deterministic, add a relationship space defining relationships between the feature and features of other families to the setlist; and

return the setlist as the list of essential sets.

13. The system of claim 10, wherein the processor is further programmed to generate the domain of a family, including to:

determine the domain space as an intersection of the restricted buildable space and a relationships work object defining a temporary object;

if a product definition indicates that the family is a deterministic family defined by at least one determinant family in the configuration, further intersect the domain space with a relationship space defining the deterministic family; and

add any of the features present in the domain space to the family domain.

14. The system of claim 10, wherein, to generate the further restricted buildable space, the processor is further programmed to:

restrict the restricted buildable space according to the Default feature; and

if the family is deterministic,

restrict a relationship space to the Default feature to determine a temporary relationship space,

generate an updated relationships work object by intersecting the relationships work object and the temporary relationship space, and

if the relationship works object has a single path, generate an updated restricted buildable space by intersecting the restricted buildable space and the relationships work object, and reset the relationship works object.

15. The system of claim 14, wherein the restricted buildable space, the relationship space and the relationship works object further comprise MDDs.

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

identify a displayable family as any family having features that are displayed to a user on a user interface; and

specify that displayable families are not deterministic.

17. 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 a minimally complete configuration including features having Selected and Included feature states;

generate a restricted buildable space of the MDD based on the minimally complete configuration;

generate a further restricted buildable space of the MDD including features having Default feature states, including

identify families that do not include features with Selected or Included feature states as families to change,

determine a weight of each path in the restricted buildable space, indicative of a priority of the features along the path based on predetermined data,

identify the maximum weight of all paths,

remove configurations having weights that are less than the maximum weight, and

for each family to change along the maximum weight path, set the highest priority feature to the Default feature state;

wherein each family along the maximum weight path includes a feature having a Selected, Included or Default feature state to generate a complete configuration.

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

19. The system of claim 18, wherein the weight of each path is represented by a bitset indicative of a sum of the weight of each feature along the path.

20. The system of claim 17, wherein the weight of each feature is defined by an alternate structure separate from the MDD.