Rethinking DESERT as a Stateless Service
OpenMETA is the flagship software tool of my company, MetaMorph, and it’s used by engineers to design complex systems such as spacecraft and automobiles. It relies on an open-source solver called DESERT to help engineers explore large design spaces. DESERT uses Multi-Terminal Ordered Binary Decision Diagrams as a highly-efficient internal way to represent the variability of a design problem, allowing it to rapidly reduce the set of possibilities using constraints that a user provides.
For example, in the UAV case study we’ll use here, we’re considering these design choices:
- Engine: Piston or Electric,
- Wingspan: 2ft, 4ft, 6ft, 8ft, 10ft, or 12ft,
- Optical Sensor Resolution: 200px², 400px², … up to 1800px²,
- Optical Sensor Field-of-View: 15deg, 30deg, … up to 90deg,
- and a few more similar decisions.
By integrating the DESERT solver, we allow designers to represent these alternative choices in OpenMETA, and then enumerate all of the permutations of the system design automatically. However, this will yield over 34,992 combinations for this use case, more than can be easily evaluated. This is where DESERT’s constraint capability comes in.
By specifying constraints on some of the properties that can be computed from these choices, we can narrow the space down to 1,784 designs that are worth analyzing further. Examples of constraints include:
- the mass must not exceed 50kg,
- the payload of the cameras must not exceed what the vehicle can carry,
- the probability of detecting vehicles at night, based on the camera properties, must be greater than 60%,
- and several more similar constraints.
Original DESERT Workflow
In a typical workflow, engineers load the whole design space into a dedicated tool, such as the Design Space Explorer UI built into OpenMETA. The engineers then progressively apply constraints until they’re reduced the space to a manageable number, then render the remaining configurations back into the original tool they were working with.
This implies a stateful way of interacting with DESERT. When a user launches a session with DESERT, we initialize the solver in the background by loading the design space data structure. Then, when the engineer chooses to apply constraints, we ask the solver to apply them and tell us how many configurations remain. When the engineer is done, we ask the solver to return the results, then unload the solver from memory.
You can run this workflow yourself using DesertTool, a standalone application built on top of the solver.
Download the DesertTool package as a ZIP file from the repository page. If you don’t have Visual Studio 2015, you’ll also need the Microsoft Visual Studio 2015 redistributable that is included there. You’ll also want the uav_example.xml project. DESERT has only been tested on Windows.
When you first run DesertTool.exe, you’ll be prompted to load a DESERT-compatible project. Select uav_example.xml.

Once the project is loaded, you’ll see the user interface at left. It lists the constraints that are available. At the bottom, it lists the No. of Cfgs, which is the number of combinations that are still in consideration. Use the Apply menu to apply the checked constraints, or all constraints, and see that figure grow smaller.
When you’re finished, exit the program. You’ll be prompted to choose a filename to save the details of the remaining configurations into an XML file.
Details of these input and output XML formats are out of scope for this discussion. However, tools such as OpenMETA that use the DESERT solver will have transforms that convert the original model into this format, and then render the remaining configurations back into the original tool.
Stateless Workflow
The previous workflow is stateful, but DESERT has some advantages that make it possible for us to use it in a stateless way.
- Loading projects is relatively fast. This loading cost is paid each time when we use it in a stateless way, but is quick enough that we can consider paying it each time we need to perform an operation.
- Constraint application is also fast. It doesn’t take long for a constraint to be applied.
- A given set of constraints always yields the same resulting configurations. Because constraint application is fast, the penalty to re-apply them each time is not bad.
If we think that we’d like to decouple the UI from the solver, and allow the solver to be used as a separate and stateless process, then there are only two invocation patterns that we need to consider:
- Load project A, apply the set of constraints B, and tell me how many configurations remain. For a given project and set of constraints, the answer will always be the same. This invocation will probably be run several times as an engineer is adding and removing constraints from consideration.
- Load project A, apply the set of constraints B, and return the resulting configurations. Again, for a given project and set of constraints, the resulting configuration set will always be the same. This invocation will probably once the engineer is satisfied that they’ve reduced the set to a manageable number of configurations.
Let’s Try It
We can do these invocations from the command line using DesertTool.exe.
Let’s try the first style of invocation, loading the project but applying no constraints:
.\DesertTool.exe .\uav_example.xml /mThe /m flag tells DESERT to return the total number of configurations with no constraints applied as well as the number of configurations remaining after all constraints applied. This is useful to get an overview of the scale of the project.
DesertTool returns control to the command-line immediately, while a new process performs the operation. This new process completes in under 1 second, producing an output XML file uav_example_configs.xml:
<?xml version="1.0"?>
<DesertConfigurations>
<None NumConfigs="34992"/>
<All NumConfigs="1784"/>
<Groups>
</Groups>
</DesertConfigurations><None NumConfigs="34992"/> means that, with None of the constraints applied, there are 34,992 configurations possible.
<All NumConfigs="1784"/> means that, with All of the constraints applied, there are 1,784 configurations possible.
Applying Specified Constraints
Let’s try applying a few specific constraints. We will take the overall mass constraint, along with the constraint that the design must be able to handle the mass of the sensor payload, and aggregate them as the Mass group.
.\DesertTool.exe .\uav_example.xml /m "__CG__Mass
:UAV_FlyWeight50Max_constraint:UAV_CanHandlePayload_constraint"Again, DesertTool returns control to the command-line immediately, while a new process performs the operation. This new process completes in under 1 second. The contents of uav_example_configs.xml now includes the number of configurations remaining after those two constraints, which is 4248:
<?xml version="1.0"?>
<DesertConfigurations>
<None NumConfigs="34992"/>
<All NumConfigs="1784"/>
<Groups>
<Group Name="Mass" NumConfigs="4248">
<Constraint Name="UAV_CanHandlePayload_constraint"/>
</Group>
</Groups>
</DesertConfigurations><Group Name="Mass" NumConfigs="4248"> means that our on-the-fly Mass group of two constraints, when applied, leave 4,248 configurations possible.
Enumerating the Remaining Configurations
With these two styles of invocation, we have enough to be able to give engineers feedback on how well they’re reducing the space. We have saved time by not asking DesertTool to enumerate the details of each remaining configuration, but simply telling us how many there are.
Next, let’s take that same set of constraints and ask DesertTool to return details of all of the resulting configurations. The difference in this command is that we use the /c flag to indicate that we want to enumerate the configurations afterwards. We also skip the group aggregation directive.
.\DesertTool.exe .\uav_example.xml /c "UAV_FlyWei
ght50Max_constraint:UAV_CanHandlePayload_constraint"Once again, DesertTool returns control to the command-line immediately, while a new process performs the operation. This process takes about 20 seconds to complete.
The result this time is two xml files. One is uav_example_configs.xml, with the same contents as the first time we ran it. The other is uav_example_back.xml, which has the enumerated list of all selected configurations. It’s too large (8 Mb) to include its entire contents, but it looks like this:
<?xml version="1.0" encoding="UTF-8" standalone="no" ?>
<DesertBackSystem SystemName="" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="DesertIfaceBack.xsd"><Configuration _id="id218" cfgId="f2ee4681" id="1" name="Conf. no: 1">
<AlternativeAssignment _id="id21F" alternative_end_="id1e1" alternative_of_end_="id1e2" externalID="-1" id="-1" name="alternative assignment"/>
<AlternativeAssignment _id="id220" alternative_end_="id1D6" alternative_of_end_="id1e3" externalID="-1" id="-1" name="alternative assignment"/>
<AlternativeAssignment _id="id221" alternative_end_="id1D3" alternative_of_end_="id1e4" externalID="-1" id="-1" name="alternative assignment"/>
<AlternativeAssignment _id="id222" alternative_end_="id1e5" alternative_of_end_="id1e6" externalID="-1" id="-1" name="alternative assignment"/>
<AlternativeAssignment _id="id223" alternative_end_="id1D8" alternative_of_end_="id1e7" externalID="-1" id="-1" name="alternative assignment"/>
<AlternativeAssignment _id="id224" alternative_end_="id1e8" alternative_of_end_="id1e9" externalID="-1" id="-1" name="alternative assignment"/>
<PropertyAssignment _id="id219" externalID="2000" id="2000" name="AssignedValues" value_end_="id1D5" value_of_end_="id1D4"/>
<PropertyAssignment _id="id21A" externalID="2000" id="2000" name="AssignedValues" value_end_="id1D5" value_of_end_="id1D7"/>
<PropertyAssignment _id="id21B" externalID="2000" id="2000" name="AssignedValues" value_end_="id1DA" value_of_end_="id1D9"/>
<PropertyAssignment _id="id21C" externalID="2000" id="2000" name="AssignedValues" value_end_="id1DC" value_of_end_="id1DB"/>
<PropertyAssignment _id="id21D" externalID="2000" id="2000" name="AssignedValues" value_end_="id1De" value_of_end_="id1DD"/>
<PropertyAssignment _id="id21e" externalID="2000" id="2000" name="AssignedValues" value_end_="id1e0" value_of_end_="id1DF"/>
</Configuration><Configuration _id="id225" cfgId="89282c5b" id="2" name="Conf. no: 2">
<AlternativeAssignment _id="id22C" alternative_end_="id1e1" alternative_of_end_="id1e2" externalID="-1" id="-1" name="alternative assignment"/>--snip--
Conclusion
In this post, we’ve talked about the difference between stateful and stateless interactions with the DESERT solver. Using DesertTool.exe, we’ve demonstrated how the stateless mode of operation can be used without incurring unacceptable performance delays. This can provide a useful abstraction for other tools that want to build on top of the solver, but in a way that is decoupled from the platform where the solver is running.