Storm 1.10.0.1
A Modern Probabilistic Model Checker
Loading...
Searching...
No Matches
ExplicitModelBuilder.cpp
Go to the documentation of this file.
2
3#include <map>
4
6
9
13
16
22
25
31
37#include "storm/utility/prism.h"
38
39namespace storm {
40namespace builder {
41
42template<typename StateType>
43StateType ExplicitStateLookup<StateType>::lookup(std::map<storm::expressions::Variable, storm::expressions::Expression> const& stateDescription) const {
44 auto cs = storm::generator::createCompressedState(this->varInfo, stateDescription, true);
45 // TODO search once
46 if (!stateToId.contains(cs)) {
47 return static_cast<StateType>(this->size());
48 }
49 return this->stateToId.getValue(cs);
50}
51
52template<typename StateType>
54 return this->stateToId.size();
55}
56
57template<typename ValueType, typename RewardModelType, typename StateType>
59 auto const& buildSettings = storm::settings::getModule<storm::settings::modules::BuildSettings>();
60 explorationOrder = buildSettings.getExplorationOrder();
61 fixDeadlocks = !buildSettings.isDontFixDeadlocksSet();
62 if (buildSettings.isExplorationStateLimitSet()) {
63 explorationStateLimit = buildSettings.getExplorationStateLimit();
64 }
65}
66
67template<typename ValueType, typename RewardModelType, typename StateType>
69 std::shared_ptr<storm::generator::NextStateGenerator<ValueType, StateType>> const& generator, Options const& options)
70 : generator(generator), options(options), stateStorage(generator->getStateSize()) {
71 // Intentionally left empty.
72}
73
74template<typename ValueType, typename RewardModelType, typename StateType>
76 storm::generator::NextStateGeneratorOptions const& generatorOptions,
77 Options const& builderOptions)
78 : ExplicitModelBuilder(std::make_shared<storm::generator::PrismNextStateGenerator<ValueType, StateType>>(program, generatorOptions), builderOptions) {
79 // Intentionally left empty.
80}
81
82template<typename ValueType, typename RewardModelType, typename StateType>
84 storm::generator::NextStateGeneratorOptions const& generatorOptions,
85 Options const& builderOptions)
86 requires(!storm::IsIntervalType<ValueType>)
87 : ExplicitModelBuilder(std::make_shared<storm::generator::JaniNextStateGenerator<ValueType, StateType>>(model, generatorOptions), builderOptions) {
88 // Intentionally left empty.
89}
90
91template<typename ValueType, typename RewardModelType, typename StateType>
92std::shared_ptr<storm::models::sparse::Model<ValueType, RewardModelType>> ExplicitModelBuilder<ValueType, RewardModelType, StateType>::build() {
93 STORM_LOG_DEBUG("Exploration order is: " << options.explorationOrder);
94
95 switch (generator->getModelType()) {
108 default:
109 STORM_LOG_THROW(false, storm::exceptions::WrongFormatException, "Error while creating model: cannot handle this model type.");
110 }
111
112 return nullptr;
113}
114
115template<typename ValueType, typename RewardModelType, typename StateType>
117 StateType newIndex = static_cast<StateType>(stateStorage.getNumberOfStates());
118
119 // Check, if the state was already registered.
120 std::pair<StateType, std::size_t> actualIndexBucketPair = stateStorage.stateToId.findOrAddAndGetBucket(state, newIndex);
121
122 StateType actualIndex = actualIndexBucketPair.first;
123
124 if (actualIndex == newIndex) {
125 if (options.explorationOrder == ExplorationOrder::Dfs) {
126 statesToExplore.emplace_front(state, actualIndex);
127
128 // Reserve one slot for the new state in the remapping.
129 stateRemapping.get().push_back(storm::utility::zero<StateType>());
130 } else if (options.explorationOrder == ExplorationOrder::Bfs) {
131 statesToExplore.emplace_back(state, actualIndex);
132 } else {
133 STORM_LOG_ASSERT(false, "Invalid exploration order.");
134 }
135 }
136
137 return actualIndex;
138}
139
140template<typename ValueType, typename RewardModelType, typename StateType>
142 return ExplicitStateLookup<StateType>(this->generator->getVariableInformation(), this->stateStorage.stateToId);
143}
144
145template<typename ValueType, typename RewardModelType, typename StateType>
147 storm::storage::SparseMatrixBuilder<ValueType>& transitionMatrixBuilder,
148 std::vector<RewardModelBuilder<typename RewardModelType::ValueType>>& rewardModelBuilders,
149 StateAndChoiceInformationBuilder& stateAndChoiceInformationBuilder) {
150 // Initialize building state valuations (if necessary)
151 if (stateAndChoiceInformationBuilder.isBuildStateValuations()) {
152 stateAndChoiceInformationBuilder.stateValuationsBuilder() = generator->initializeStateValuationsBuilder();
153 }
154
155 // Create a callback for the next-state generator to enable it to request the index of states.
156 std::function<StateType(CompressedState const&)> stateToIdCallback =
157 std::bind(&ExplicitModelBuilder<ValueType, RewardModelType, StateType>::getOrAddStateIndex, this, std::placeholders::_1);
158
159 // If the exploration order is something different from breadth-first, we need to keep track of the remapping
160 // from state ids to row groups. For this, we actually store the reversed mapping of row groups to state-ids
161 // and later reverse it.
162 if (options.explorationOrder != ExplorationOrder::Bfs) {
163 stateRemapping = std::vector<uint_fast64_t>();
164 }
165
166 // Let the generator create all initial states.
167 this->stateStorage.initialStateIndices = generator->getInitialStates(stateToIdCallback);
168 STORM_LOG_THROW(!this->stateStorage.initialStateIndices.empty(), storm::exceptions::WrongFormatException,
169 "The model does not have a single initial state.");
170
171 // Now explore the current state until there is no more reachable state.
172 uint_fast64_t currentRowGroup = 0;
173 uint_fast64_t currentRow = 0;
174
175 auto timeOfStart = std::chrono::high_resolution_clock::now();
176 auto timeOfLastMessage = std::chrono::high_resolution_clock::now();
177 uint64_t numberOfExploredStates = 0;
178 uint64_t numberOfExploredStatesSinceLastMessage = 0;
179
180 // Perform a search through the model.
181 while (!statesToExplore.empty()) {
182 // Get the first state in the queue.
183 CompressedState currentState = statesToExplore.front().first;
184 StateType currentIndex = statesToExplore.front().second;
185 statesToExplore.pop_front();
186
187 // If the exploration order differs from breadth-first, we remember that this row group was actually
188 // filled with the transitions of a different state.
189 if (options.explorationOrder != ExplorationOrder::Bfs) {
190 stateRemapping.get()[currentIndex] = currentRowGroup;
191 }
192
193 if (currentIndex % 100000 == 0) {
194 STORM_LOG_TRACE("Exploring state with id " << currentIndex << ".");
195 }
196
197 generator->load(currentState);
198 if (stateAndChoiceInformationBuilder.isBuildStateValuations()) {
199 generator->addStateValuation(currentIndex, stateAndChoiceInformationBuilder.stateValuationsBuilder());
200 }
201
203 // If the exploration state limit is set and the limit is reached, we stop the exploration.
204 bool const stateLimitExceeded = options.explorationStateLimit.has_value() && stateStorage.getNumberOfStates() >= options.explorationStateLimit.value();
205 if (!stateLimitExceeded) {
206 behavior = generator->expand(stateToIdCallback);
207 }
208
209 if (behavior.empty()) {
210 // There are three possible cases for missing behavior:
211 if (behavior.wasExpanded()) {
212 // (a) The state is a deadlock state, i.e. there is no behavior even though the state was expanded
213 STORM_LOG_THROW(options.fixDeadlocks, storm::exceptions::WrongFormatException,
214 "Error while creating sparse matrix from probabilistic program: found deadlock state ("
215 << generator->stateToString(currentState) << "). For fixing these, please provide the appropriate option.");
216 this->stateStorage.deadlockStateIndices.push_back(currentIndex);
217 } else {
218 if (stateLimitExceeded) {
219 // (b) The state was not expanded because the state limit is reached
220 this->stateStorage.unexploredStateIndices.push_back(currentIndex);
221 }
222 // (c) the state was not expanded because it is terminal, i.e., exploration from that state is not required for the given property/ies
223 }
224
225 // In all cases, we need to add a self-loop to the transition matrix.
226
227 if (!generator->isDeterministicModel()) {
228 transitionMatrixBuilder.newRowGroup(currentRow);
229 }
230
231 transitionMatrixBuilder.addNextValue(currentRow, currentIndex, storm::utility::one<ValueType>());
232
233 for (auto& rewardModelBuilder : rewardModelBuilders) {
234 if (rewardModelBuilder.hasStateRewards()) {
235 rewardModelBuilder.addStateReward(storm::utility::zero<ValueType>());
236 }
237
238 if (rewardModelBuilder.hasStateActionRewards()) {
239 rewardModelBuilder.addStateActionReward(storm::utility::zero<ValueType>());
240 }
241 }
242
243 // This state shall be Markovian (to not introduce Zeno behavior)
244 if (stateAndChoiceInformationBuilder.isBuildMarkovianStates()) {
245 stateAndChoiceInformationBuilder.addMarkovianState(currentRowGroup);
246 }
247 // Other state-based information does not need to be treated, in particular:
248 // * StateValuations have already been set above
249 // * The associated player shall be the "default" player, i.e. INVALID_PLAYER_INDEX
250
251 ++currentRow;
252 ++currentRowGroup;
253 } else {
254 // Add the state rewards to the corresponding reward models.
255 auto stateRewardIt = behavior.getStateRewards().begin();
256 for (auto& rewardModelBuilder : rewardModelBuilders) {
257 if (rewardModelBuilder.hasStateRewards()) {
258 rewardModelBuilder.addStateReward(*stateRewardIt);
259 }
260 ++stateRewardIt;
261 }
262
263 // If the model is nondeterministic, we need to open a row group.
264 if (!generator->isDeterministicModel()) {
265 transitionMatrixBuilder.newRowGroup(currentRow);
266 }
267
268 // Now add all choices.
269 bool firstChoiceOfState = true;
270 for (auto const& choice : behavior) {
271 // add the generated choice information
272 if (stateAndChoiceInformationBuilder.isBuildChoiceLabels() && choice.hasLabels()) {
273 for (auto const& label : choice.getLabels()) {
274 stateAndChoiceInformationBuilder.addChoiceLabel(label, currentRow);
275 }
276 }
277 if (stateAndChoiceInformationBuilder.isBuildChoiceOrigins() && choice.hasOriginData()) {
278 stateAndChoiceInformationBuilder.addChoiceOriginData(choice.getOriginData(), currentRow);
279 }
280 if (stateAndChoiceInformationBuilder.isBuildStatePlayerIndications() && choice.hasPlayerIndex()) {
282 firstChoiceOfState || stateAndChoiceInformationBuilder.hasStatePlayerIndicationBeenSet(choice.getPlayerIndex(), currentRowGroup),
283 "There is a state where different players have an enabled choice."); // Should have been detected in generator, already
284 if (firstChoiceOfState) {
285 stateAndChoiceInformationBuilder.addStatePlayerIndication(choice.getPlayerIndex(), currentRowGroup);
286 }
287 }
288 if (stateAndChoiceInformationBuilder.isBuildMarkovianStates() && choice.isMarkovian()) {
289 stateAndChoiceInformationBuilder.addMarkovianState(currentRowGroup);
290 }
291
292 // Add the probabilistic behavior to the matrix.
293 for (auto const& stateProbabilityPair : choice) {
294 transitionMatrixBuilder.addNextValue(currentRow, stateProbabilityPair.first, stateProbabilityPair.second);
295 }
296
297 // Add the rewards to the reward models.
298 auto choiceRewardIt = choice.getRewards().begin();
299 for (auto& rewardModelBuilder : rewardModelBuilders) {
300 if (rewardModelBuilder.hasStateActionRewards()) {
301 rewardModelBuilder.addStateActionReward(*choiceRewardIt);
302 }
303 ++choiceRewardIt;
304 }
305 ++currentRow;
306 firstChoiceOfState = false;
307 }
308
309 ++currentRowGroup;
310 }
311
312 ++numberOfExploredStates;
313 if (generator->getOptions().isShowProgressSet()) {
314 ++numberOfExploredStatesSinceLastMessage;
315
316 auto now = std::chrono::high_resolution_clock::now();
317 auto durationSinceLastMessage = std::chrono::duration_cast<std::chrono::seconds>(now - timeOfLastMessage).count();
318 if (static_cast<uint64_t>(durationSinceLastMessage) >= generator->getOptions().getShowProgressDelay()) {
319 auto statesPerSecond = numberOfExploredStatesSinceLastMessage / durationSinceLastMessage;
320 auto durationSinceStart = std::chrono::duration_cast<std::chrono::seconds>(now - timeOfStart).count();
321 std::cout << "Explored " << numberOfExploredStates << " states in " << durationSinceStart << " seconds (currently " << statesPerSecond
322 << " states per second).\n";
323 timeOfLastMessage = std::chrono::high_resolution_clock::now();
324 numberOfExploredStatesSinceLastMessage = 0;
325 }
326 }
327
329 auto durationSinceStart = std::chrono::duration_cast<std::chrono::seconds>(std::chrono::high_resolution_clock::now() - timeOfStart).count();
330 std::cout << "Explored " << numberOfExploredStates << " states in " << durationSinceStart << " seconds before abort.\n";
331 STORM_LOG_THROW(false, storm::exceptions::AbortException, "Aborted in state space exploration.");
332 break;
333 }
334 }
335
336 // If the exploration order was not breadth-first, we need to fix the entries in the matrix according to
337 // (reversed) mapping of row groups to indices.
338 if (options.explorationOrder != ExplorationOrder::Bfs) {
339 STORM_LOG_ASSERT(stateRemapping, "Unable to fix columns without mapping.");
340 std::vector<uint_fast64_t> const& remapping = stateRemapping.get();
341
342 // We need to fix the following entities:
343 // (a) the transition matrix
344 // (b) the initial states
345 // (c) the hash map storing the mapping states -> ids
346 // (d) fix remapping for state-generation labels
347
348 // Fix (a).
349 transitionMatrixBuilder.replaceColumns(remapping, 0);
350
351 // Fix (b).
352 std::vector<StateType> newInitialStateIndices(this->stateStorage.initialStateIndices.size());
353 std::transform(this->stateStorage.initialStateIndices.begin(), this->stateStorage.initialStateIndices.end(), newInitialStateIndices.begin(),
354 [&remapping](StateType const& state) { return remapping[state]; });
355 std::sort(newInitialStateIndices.begin(), newInitialStateIndices.end());
356 this->stateStorage.initialStateIndices = std::move(newInitialStateIndices);
357
358 // Fix (c).
359 this->stateStorage.stateToId.remap([&remapping](StateType const& state) { return remapping[state]; });
360
361 this->generator->remapStateIds([&remapping](StateType const& state) { return remapping[state]; });
362 }
363}
364
365template<typename ValueType, typename RewardModelType, typename StateType>
366storm::storage::sparse::ModelComponents<ValueType, RewardModelType> ExplicitModelBuilder<ValueType, RewardModelType, StateType>::buildModelComponents() {
367 // Determine whether we have to combine different choices to one or whether this model can have more than
368 // one choice per state.
369 bool deterministicModel = generator->isDeterministicModel();
370
371 // Prepare the component builders
372 storm::storage::SparseMatrixBuilder<ValueType> transitionMatrixBuilder(0, 0, 0, false, !deterministicModel, 0);
373 std::vector<RewardModelBuilder<typename RewardModelType::ValueType>> rewardModelBuilders;
374 for (uint64_t i = 0; i < generator->getNumberOfRewardModels(); ++i) {
375 rewardModelBuilders.emplace_back(generator->getRewardModelInformation(i));
376 }
377 StateAndChoiceInformationBuilder stateAndChoiceInformationBuilder;
378 stateAndChoiceInformationBuilder.setBuildChoiceLabels(generator->getOptions().isBuildChoiceLabelsSet());
379 stateAndChoiceInformationBuilder.setBuildChoiceOrigins(generator->getOptions().isBuildChoiceOriginsSet());
380 stateAndChoiceInformationBuilder.setBuildStatePlayerIndications(generator->getModelType() == storm::generator::ModelType::SMG);
381 stateAndChoiceInformationBuilder.setBuildMarkovianStates(generator->getModelType() == storm::generator::ModelType::MA);
382 stateAndChoiceInformationBuilder.setBuildStateValuations(generator->getOptions().isBuildStateValuationsSet());
383
384 buildMatrices(transitionMatrixBuilder, rewardModelBuilders, stateAndChoiceInformationBuilder);
385
386 // Initialize the model components with the obtained information.
388 transitionMatrixBuilder.build(0, transitionMatrixBuilder.getCurrentRowGroupCount()), buildStateLabeling(),
389 std::unordered_map<std::string, RewardModelType>(), !generator->isDiscreteTimeModel());
390
391 uint_fast64_t numStates = modelComponents.transitionMatrix.getColumnCount();
392 uint_fast64_t numChoices = modelComponents.transitionMatrix.getRowCount();
393
394 // Now finalize all reward models.
395 for (auto& rewardModelBuilder : rewardModelBuilders) {
396 modelComponents.rewardModels.emplace(rewardModelBuilder.getName(),
397 rewardModelBuilder.build(numChoices, modelComponents.transitionMatrix.getColumnCount(), numStates));
398 }
399 // Build the player assignment
400 if (stateAndChoiceInformationBuilder.isBuildStatePlayerIndications()) {
401 modelComponents.statePlayerIndications = stateAndChoiceInformationBuilder.buildStatePlayerIndications(numStates);
402 modelComponents.playerNameToIndexMap = generator->getPlayerNameToIndexMap();
403 }
404 // Build Markovian states
405 if (stateAndChoiceInformationBuilder.isBuildMarkovianStates()) {
406 modelComponents.markovianStates = stateAndChoiceInformationBuilder.buildMarkovianStates(numStates);
407 }
408 // Build the choice labeling
409 if (stateAndChoiceInformationBuilder.isBuildChoiceLabels()) {
410 modelComponents.choiceLabeling = stateAndChoiceInformationBuilder.buildChoiceLabeling(numChoices);
411 }
412 // If requested, build the state valuations and choice origins
413 if (stateAndChoiceInformationBuilder.isBuildStateValuations()) {
414 modelComponents.stateValuations = stateAndChoiceInformationBuilder.stateValuationsBuilder().build();
415 }
416 if (stateAndChoiceInformationBuilder.isBuildChoiceOrigins()) {
417 auto originData = stateAndChoiceInformationBuilder.buildDataOfChoiceOrigins(numChoices);
418 modelComponents.choiceOrigins = generator->generateChoiceOrigins(originData);
419 }
420 if (generator->isPartiallyObservable()) {
421 std::vector<uint32_t> classes(stateStorage.getNumberOfStates());
422 std::unordered_map<uint32_t, std::vector<std::pair<std::vector<std::string>, uint32_t>>> observationActions;
423 for (auto const& bitVectorIndexPair : stateStorage.stateToId) {
424 uint32_t varObservation = generator->observabilityClass(bitVectorIndexPair.first);
425 classes[bitVectorIndexPair.second] = varObservation;
426 }
427
428 modelComponents.observabilityClasses = classes;
429 if (generator->getOptions().isBuildObservationValuationsSet()) {
430 modelComponents.observationValuations = generator->makeObservationValuation();
431 }
432 }
433 return modelComponents;
434}
435
436template<typename ValueType, typename RewardModelType, typename StateType>
437storm::models::sparse::StateLabeling ExplicitModelBuilder<ValueType, RewardModelType, StateType>::buildStateLabeling() {
438 return generator->label(stateStorage, stateStorage.initialStateIndices, stateStorage.deadlockStateIndices, stateStorage.unexploredStateIndices);
439}
440
441// Explicitly instantiate the class.
442template class ExplicitModelBuilder<double, storm::models::sparse::StandardRewardModel<double>, uint32_t>;
443template class ExplicitStateLookup<uint32_t>;
444
445template class ExplicitModelBuilder<RationalNumber, storm::models::sparse::StandardRewardModel<RationalNumber>, uint32_t>;
446template class ExplicitModelBuilder<RationalFunction, storm::models::sparse::StandardRewardModel<RationalFunction>, uint32_t>;
447template class ExplicitModelBuilder<double, storm::models::sparse::StandardRewardModel<storm::Interval>, uint32_t>; // TODO: where is this used?
448template class ExplicitModelBuilder<storm::Interval, storm::models::sparse::StandardRewardModel<storm::Interval>, uint32_t>;
449
450} // namespace builder
451} // namespace storm
ExplicitStateLookup< StateType > exportExplicitStateLookup() const
Export a wrapper that contains (a copy of) the internal information that maps states to ids.
ExplicitModelBuilder(std::shared_ptr< storm::generator::NextStateGenerator< ValueType, StateType > > const &generator, Options const &options=Options())
Creates an explicit model builder that uses the provided generator.
std::shared_ptr< storm::models::sparse::Model< ValueType, RewardModelType > > build()
Convert the program given at construction time to an abstract model.
StateType lookup(std::map< storm::expressions::Variable, storm::expressions::Expression > const &stateDescription) const
Lookup state.
uint64_t size() const
How many states have been stored?
A structure that is used to keep track of a reward model currently being built.
This class collects information regarding the states and choices during model building.
storm::storage::sparse::StateValuationsBuilder & stateValuationsBuilder()
bool hasStatePlayerIndicationBeenSet(storm::storage::PlayerIndex expectedPlayer, uint_fast64_t stateIndex) const
void addStatePlayerIndication(storm::storage::PlayerIndex player, uint_fast64_t stateIndex)
void addChoiceLabel(std::string const &label, uint_fast64_t choiceIndex)
void addChoiceOriginData(boost::any const &originData, uint_fast64_t choiceIndex)
bool empty() const
Retrieves whether the behavior is empty in the sense that there are no available choices.
bool wasExpanded() const
Retrieves whether the state was expanded.
std::vector< ValueType > const & getStateRewards() const
Retrieves the list of state rewards under selected reward models.
This class manages the labeling of the state space with a number of (atomic) labels.
A bit vector that is internally represented as a vector of 64-bit values.
Definition BitVector.h:16
bool get(uint64_t index) const
Retrieves the truth value of the bit at the given index and performs a bound check.
A class that can be used to build a sparse matrix by adding value by value.
index_type getCurrentRowGroupCount() const
Retrieves the current row group count.
void addNextValue(index_type row, index_type column, value_type const &value)
Sets the matrix entry at the given row and column to the given value.
void replaceColumns(std::vector< index_type > const &replacements, index_type offset)
Replaces all columns with id > offset according to replacements.
void newRowGroup(index_type startingRow)
Starts a new row group in the matrix.
SparseMatrix< value_type > build(index_type overriddenRowCount=0, index_type overriddenColumnCount=0, index_type overriddenRowGroupCount=0)
#define STORM_LOG_DEBUG(message)
Definition logging.h:18
#define STORM_LOG_TRACE(message)
Definition logging.h:12
#define STORM_LOG_ASSERT(cond, message)
Definition macros.h:11
#define STORM_LOG_THROW(cond, exception, message)
Definition macros.h:30
CompressedState createCompressedState(VariableInformation const &varInfo, std::map< storm::expressions::Variable, storm::expressions::Expression > const &stateDescription, bool checkOutOfBounds)
storm::storage::BitVector CompressedState
std::shared_ptr< storm::models::sparse::Model< ValueType, RewardModelType > > buildModelFromComponents(storm::models::ModelType modelType, storm::storage::sparse::ModelComponents< ValueType, RewardModelType > &&components)
Definition builder.cpp:19
bool isTerminate()
Check whether the program should terminate (due to some abort signal).
LabParser.cpp.
Options()
Creates an object representing the default building options.