Multi-valued decision diagram feature state determination

• US 10,325,063 B2
• Filed: 10/14/2016
• Issued: 06/18/2019
• Est. Priority Date: 01/19/2016
• Status: Active Grant

• Current Assignee: Ford Motor Company
• Original Assignee: Ford Motor Company
• Inventors: Hunsaker, Melinda Kaye, Newton, David Mark, Sabbagh, Essam Mahmoud
• Primary Examiner(s): Thangavelu, Kandasamy
• Application Number:
  US15/294,217
• Publication Number:
  US 20170206576A1
• Time in Patent Office: 977 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 memory and a processor. The memory is configured to store data representative of a multi-valued decision diagram (MDD). The processor is in communication with the memory and is programmed to receive a current selection of one or more of the features, and to determine a feature state for each of the one or more features, based on the current selection and the possible configurations defined by the MDD. The processor is further programmed to calculate an availability bitset indicative of which features as available for further selection, consistent with the valid configurations and without violating existing constraints of the current selection.

Claims

1. A method to determine feature states comprising:

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

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;

generating an availability bitset indicative of which features are available for further selection, consistent with the valid configuration and without violating constraints imposed by the current selection;

determining a feature state for all features based on the current selection and the availability bitset;

presenting to the user features possible for selection, based on the availability bitset;

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;

regenerating the availability bitset indicative of which features are available for further selection, consistent with the valid configuration and without violating constraints imposed by the current selection; and

repeating the process starting from presenting to the user the features possible for selection by the user until all families are included in the valid configuration.

2. The method of claim 1, wherein the availability bitset indicates a first value of ‘

1’

for a feature when the feature is available for selection without violating the constraints imposed by the current selection, and a second value of ‘

0’

for the feature when the feature is excluded and not available for selection due to violating the constraints imposed by the current selection if selected.

3. The method of claim 1, wherein the feature state for each of the features indicates one of:

(i) selected for a feature that has been explicitly selected by a user,

(ii) available for a feature that is free for selection without violating the constraints imposed by the current selection,

(iii) included for a feature that is the only available choice in a family due to user selection of one or more features that require it,

(iv) default for a feature that is selected due to automatic completion of the configuration,

(v) excluded for a feature that conflicts with existing constraints, and

(vi) forbidden for a feature that violates an external constraint independent of the possible configurations specified by the MDD that cannot be resolved if selected.

4. The method of claim 3, wherein the external constraint is a feature that is unavailable for manufacture at a particular time.

5. The method of claim 1, farther comprising:

performing a downward traversal of the MDD from the root node to identify downward-marked nodes that are not excluded by the selection;

performing an upward traversal of the MDD from the truth node to identify upward-marked nodes that are not excluded by the selection; and

generating the availability bitset by identifying the features available for further selection, consistent with the valid configuration and without violating constraints imposed by the current selection, as the nodes that are both downward-marked and upward-marked.

6. The method of claim 1, further comprising:

performing a first restricted domain calculation using the feature state to identify which additional feature selections outside of the families having feature selections are compatible with the current selection;

performing, for each family in which a feature is selected, a second restricted domain calculation to identify which additional features in that family are compatible with the current selection; and

generating the availability bitset by identifying the features available for further selection according to the first and the second restricted domain calculations.

7. The method of claim 1, further comprising identifying a feature as excluded by the selection when the feature is not selected or available.

8. The method of claim 7. further comprising identifying an included feature as a feature that is unselected but included in a family having exactly one available feature.

9. A system comprising:

a memory configured to store data representative of a multi-valued decision diagram (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 and represented by at least one node, each node of a level 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, 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

receive 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,

generate an availability bitset indicative of which features are available for further selection, consistent with the valid configuration and without violating constraints imposed by the current selection,

determine a feature state for all features based on the current selection and the availability bitset,

present to the user features possible for selection, based on the availability bitset,

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

perform validation of the new partial configuration using a configuration engine,

if the new partial configuration is invalid, prompt the user to make changes, or allow the configuration engine to make the changes according to a predefined hierarchy,

set the new partial configuration as the partial configuration and the current selection,

regenerate the availability bitset indicative of which features are available for further selection, consistent with the valid configuration and without violating constraints imposed by the current selection, and

repeat the process starting from presenting to the user the features possible for selection by the user until all families are included m the valid configuration.

10. The system of claim 9, wherein the availability bitset indicates a first value of ‘

1’

for a feature when the feature is available for selection without violating the constraints imposed by the current selection, and a second value of ‘

0’

for the feature when the feature is excluded and not available for selection due to violating the constraints imposed by the current selection if selected.

11. The system of claim 9, wherein the feature state for each of the one or more features indicates one of:

(i) selected for a feature that has been explicitly selected by a user,

(ii) available for a feature that is free for selection without violating the constraints imposed by the current selection,

(iii) included for a feature that is the only available choice in a family due to user selection of one or more features that require it,

(iv) default for a feature that is selected due to automatic completion of the configuration,

(v) excluded for a feature that conflicts with existing constraints, and

(vi) forbidden for a feature that violates an external constraint independent of the possible configurations specified by the MDD that cannot be resolved if selected.

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

perform a downward traversal of the MDD from the root node to identify downward-marked nodes that are not excluded by the selection;

perform an upward traversal of the MDD from the truth node to identify upward-marked nodes that are not excluded by the selection; and

generate the availability bitset by identifying the features available for further selection, consistent with the valid configuration and without violating constraints imposed by the current selection, as the nodes that are both downward-marked and upward-marked.

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

perform a first restricted domain calculation using the feature state to identify which additional feature selections outside of the families having feature selections are compatible with the current selection;

perform, for each family in which a feature is selected, a second restricted domain calculation to identify which additional features in that family are compatible with the current selection; and

generate the availability bitset by identifying the features available for further selection according to the first and the second restricted domain calculations.

14. The system of claim 9, Wherein the processor is further programmed to:

identify a feature as excluded by the selection when the feature is not selected or available; and

identify an included feature as a feature that is unselected but included in a family having exactly one available feature.

15. A non-transitory computer-readable medium comprising instructions that, when executed by a processor, cause the processor to:

store data representative of a multi-valued decision diagram (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 and represented by at least one node, each node of a level 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, 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;

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

generate an availability bitset indicative of which features are available for further selection, consistent with the valid configuration and without violating constraints imposed by the current selection;

determine a feature state for all features based on the current selection and the availability bitset;

present to the user features possible for selection, based on the availability bitset;

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

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

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

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

regenerate the availability bitset indicative of which features are available for further selection, consistent with the valid configuration and without violating constraints imposed by the current selection; and

repeat the process starting from presenting to the user the features possible for selection by the user until all families are included in the valid configuration.

16. The medium of claim 15, wherein the availability bitset indicates a first value of ‘

1’

for a feature when the feature is available for selection without violating the constraints imposed by the current selection, and a second value of ‘

0’

for the feature when the feature is excluded and not available for selection due to violating the constraints imposed by the current selection if selected.

17. The medium of claim 15, wherein the feature state for each of the one or more features indicates one of:

(i) selected for a feature that has been explicitly selected by a user,

(ii) available for a feature that is free for selection without violating the constraints imposed by the current selection,

(iii) included for a feature that that is the only available choice in a family due to user selection of one or more features that require it,

(iv) default for a feature that is selected due to automatic completion of the configuration,

(v) excluded for a feature that conflicts with existing constraints, and

(vi) forbidden for a feature that violates an external constraint independent of the possible configurations specified by the MDD that cannot be resolved if selected.

18. The medium of claim 15, further comprising instructions that, when executed by a processor, cause the processor to:

perform a downward traversal of the MDD from the root node to identify downward-marked nodes that are not excluded by the selection;

perform an upward traversal of the MDD from the truth node to identify upward-marked nodes that are not excluded by the selection; and

generate the availability bitset by identifying the features available for further selection, consistent with the valid configuration and without violating constraints imposed by the current selection, as the nodes that are both downward-marked and upward-marked.

19. The medium of claim 15, further comprising instructions that, when executed by a processor, cause the processor to:

perform a first restricted domain calculation using the feature stale to identify which additional feature selections outside of the families having feature selections are compatible with the current selection;

perform, for each family in which a feature is selected, a second restricted domain calculation to identify which additional features in that family are compatible with the current selection; and

generate the availability bitset by identifying the features available for further selection according to the first and second restricted domain calculations.

20. The medium of claim 15, further comprising:

instructions that, when executed by a processor, cause the processor to identify a feature as excluded by the selection when the feature is not selected or available; and

instructions that, when executed by a processor, cause the processor to identify an included feature as a feature that is unselected but included in a family having exactly one available feature.