Multi-valued decision diagram reversible restriction

• US 10,318,702 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, Sprague, Rickie Allan
• Primary Examiner(s): Thangavelu, Kandasamy
• Application Number:
  US15/294,330
• Publication Number:
  US 20170206577A1
• 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 and a processor. The memory is configured to store a cached copy of data representative of a multi-valued decision diagram (MDD). The MDD indicates a Boolean function specifying a buildable space of all possible configurations of features of a vehicle. The processor is in communication with the memory, and programmed to generate a working copy of the data from the cache. The processor is further programmed to generate a restricted buildable space in the working copy of the data while traversing the MDD, including to remove available features from the labels of the outgoing edges deemed invalid according to a feature selection, disconnect outgoing edges having no remaining available features, and replace nodes that have no outgoing edges with the false node.

Claims

1. A method comprising:

storing, in a memory, a cached copy of data representative of a multi-valued decision diagram (MDD), the MDD indicating a Boolean function specifying a buildable space of all possible configurations of features of a vehicle, the MDD including a root node, a truth node, a false node, and at least one level of intervening nodes between the root node and either the truth node or the false node, each level of the MDD corresponding to a family of mutually-exclusive features represented by at least one node, each node except for the truth node and the false node connecting to nodes of a next adjacent level by outgoing edges having labels each indicating one or more features of the family that are available for the possible configurations including the node, each node except for the root node connecting 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 one valid configuration, wherein each complete path from the root node to the truth node is of the same length in nodes when there are no long edges;

generating a working copy of the data from the cache; and

generating a restricted buildable space in the working copy of the data while traversing the MDD by

receiving from a user a current selection of a partial configuration comprising one or more families with one feature selected for each family, wherein the partial configuration has been validated as a valid configuration,

identifying from the labels of the outgoing edges those features that would result in an invalid configuration of the vehicle,

removing those identified features from the MDD by pointing corresponding outgoing edges to the false node,

disconnecting outgoing edges having no remaining available features, and

replacing nodes that have no outgoing edges with the false node by pointing corresponding incoming edges to the false node;

generating a domain for the restricted buildable space as defining all of the available features of the vehicle according to the remaining connected nodes of the MDD;

presenting to the user features available for selection;

receiving from the user, selection of one of the available features for a next family and setting that feature in the partial configuration as Selected resulting in a new partial configuration;

performing validation of the new partial configuration using a configuration engine;

if the new partial configuration is invalid, prompting the user to make changes, or allowing the configuration engine to make the changes according to a predefined hierarchy;

setting the new partial configuration as the partial configuration and the current selection; and

repeating the process starting from generating a restricted buildable space in the working copy of the data until all families are included in the valid configuration.

2. The method of claim 1, wherein generating the domain is performed within the same traversal of the MDD generating the restricted buildable space.

3. The method of claim 2, wherein generating the domain and restricted buildable space is performed using a single depth-first traversal of the MDD.

4. The method of claim 1, wherein for each level of intermediate nodes, each outgoing label of a node indicates a bitset specifying a bit for each mutually-exclusive feature of the family of features of the level of the node, such that available feature are indicated in the bitset by a first value, and unavailable features are indicated in the bitset by a second value.

5. The method of claim 4, wherein disconnecting outgoing edges having no remaining available features includes disconnecting outgoing edges having outgoing labels indicating bitsets where the value of each feature in the bitset is the second value.

6. The method of claim 1, further comprising:

saving, to the memory, the edges of the working copy of the MDD before generating the restricted buildable space; and

restoring the buildable space of all possible configurations by copying the saved edges from the memory back to the working copy of the MDD.

7. The method of claim 1, further comprising responsive to a request to a configurator application, creating the working copy of the MDD by copying each node and each outgoing edge of the MDD.

8. A system comprising:

a memory configured to store a cached copy of data representative of a multi-valued decision diagram (MDD), the MDD indicating a Boolean function specifying a buildable space of all possible configurations of features of a vehicle, the MDD including a root node, a truth node, a false node, and at least one level of intervening nodes between the root node and either the truth node or the false node, each level of the MDD corresponding to a family of mutually-exclusive features represented by at least one node, each node except for the truth node and the false node connecting to nodes of a next adjacent level by outgoing edges having labels each indicating one or more features of the family that are available for the possible configurations including the node, each node except for the root node connecting 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 one valid configuration, wherein each complete path from the root node to the truth node is of the same length in nodes when there are no long edges; and

a processor in communication with the memory, programmed to;

generate a working copy of the data from the cache; and

generate a restricted buildable space in the working copy of the data while traversing the MDD by

receiving

from a user a current selection of a partial configuration comprising one or more families with one feature selected for each family, wherein the partial configuration has been validated as a valid configuration,

identifying from the labels of the outgoing edges those features that would result in an invalid configuration of the vehicle,

removing those identified features from the MDD by pointing corresponding outgoing edges to the false node,

disconnecting outgoing edges having no remaining available features, and

replacing nodes that have no outgoing edges with the false node by pointing corresponding incoming edges to the false node;

generating a domain for the restricted buildable space as defining all of the available features of the vehicle according to the remaining connected nodes of the MDD;

presenting to the user features available for selection;

receiving from the user, selection of one of the possible features for a next family and setting that feature in the partial configuration as Selected resulting in a new partial configuration;

performing validation of the new partial configuration using a configuration engine;

if the new partial configuration is invalid, prompting the user to make changes, or allowing the configuration engine to make the changes according to a predefined hierarchy;

setting the new partial configuration as the partial configuration and the current selection; and

repeating the process starting from generating a restricted buildable space in the working copy of the data until all families are included in the valid configuration.

9. The system of claim 8, wherein the processor is further programmed to generate the domain, within the same traversal of the MDD generating the restricted buildable space.

10. The system of claim 8, wherein generating the domain and restricted buildable space is performed using a single depth-first traversal of the MDD.

11. The system of claim 8, wherein for each level of intermediate nodes, each outgoing label of a node indicates a bitset specifying a bit for each mutually-exclusive feature of the family of features of the level of the node, such that available feature are indicated in the bitset by a first value, and unavailable features are indicated in the bitset by a second value.

12. The system of claim 11, wherein disconnecting outgoing edges having no remaining available features includes to disconnect outgoing edges having outgoing labels indicating bitsets where the value of each feature in the bitset is the second value.

13. The system of claim 8, wherein the processor is further programmed to:

save, to the memory, the edges of the working copy of the MDD before generating the restricted buildable space; and

restore the buildable space of all possible configurations by copying the saved edges from the memory back to the working copy of the MDD.

14. The system of claim 8, wherein the processor is further programmed to, responsive to a request to a configurator application, create the working copy of the MDD by copying each node and each outgoing edge of the MDD.

15. The system of claim 8, wherein the processor is further programmed to expand long edges of the working copy prior to generating the restricted buildable space.