42template<
typename StateType>
46 if (!stateToId.contains(cs)) {
47 return static_cast<StateType
>(this->size());
49 return this->stateToId.getValue(cs);
52template<
typename StateType>
54 return this->stateToId.size();
57template<
typename ValueType,
typename RewardModelType,
typename StateType>
59 auto const& buildSettings = storm::settings::getModule<storm::settings::modules::BuildSettings>();
62 if (buildSettings.isExplorationStateLimitSet()) {
67template<
typename ValueType,
typename RewardModelType,
typename StateType>
70 : generator(generator), options(options), stateStorage(generator->getStateSize()) {
74template<
typename ValueType,
typename RewardModelType,
typename StateType>
82template<
typename ValueType,
typename RewardModelType,
typename StateType>
86 requires(!storm::IsIntervalType<ValueType>)
91template<
typename ValueType,
typename RewardModelType,
typename StateType>
95 switch (generator->getModelType()) {
109 STORM_LOG_THROW(
false, storm::exceptions::WrongFormatException,
"Error while creating model: cannot handle this model type.");
115template<
typename ValueType,
typename RewardModelType,
typename StateType>
117 StateType newIndex =
static_cast<StateType
>(stateStorage.getNumberOfStates());
120 std::pair<StateType, std::size_t> actualIndexBucketPair = stateStorage.stateToId.findOrAddAndGetBucket(state, newIndex);
122 StateType actualIndex = actualIndexBucketPair.first;
124 if (actualIndex == newIndex) {
126 statesToExplore.emplace_front(state, actualIndex);
129 stateRemapping.get().push_back(storm::utility::zero<StateType>());
131 statesToExplore.emplace_back(state, actualIndex);
140template<
typename ValueType,
typename RewardModelType,
typename StateType>
145template<
typename ValueType,
typename RewardModelType,
typename StateType>
152 stateAndChoiceInformationBuilder.
stateValuationsBuilder() = generator->initializeStateValuationsBuilder();
157 std::bind(&ExplicitModelBuilder<ValueType, RewardModelType, StateType>::getOrAddStateIndex,
this, std::placeholders::_1);
163 stateRemapping = std::vector<uint_fast64_t>();
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.");
172 uint_fast64_t currentRowGroup = 0;
173 uint_fast64_t currentRow = 0;
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;
181 while (!statesToExplore.empty()) {
184 StateType currentIndex = statesToExplore.front().second;
185 statesToExplore.pop_front();
190 stateRemapping.
get()[currentIndex] = currentRowGroup;
193 if (currentIndex % 100000 == 0) {
197 generator->load(currentState);
204 bool const stateLimitExceeded = options.explorationStateLimit.has_value() && stateStorage.getNumberOfStates() >= options.explorationStateLimit.value();
205 if (!stateLimitExceeded) {
206 behavior = generator->expand(stateToIdCallback);
209 if (behavior.
empty()) {
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);
218 if (stateLimitExceeded) {
220 this->stateStorage.unexploredStateIndices.push_back(currentIndex);
227 if (!generator->isDeterministicModel()) {
231 transitionMatrixBuilder.
addNextValue(currentRow, currentIndex, storm::utility::one<ValueType>());
233 for (
auto& rewardModelBuilder : rewardModelBuilders) {
234 if (rewardModelBuilder.hasStateRewards()) {
235 rewardModelBuilder.addStateReward(storm::utility::zero<ValueType>());
238 if (rewardModelBuilder.hasStateActionRewards()) {
239 rewardModelBuilder.addStateActionReward(storm::utility::zero<ValueType>());
256 for (
auto& rewardModelBuilder : rewardModelBuilders) {
257 if (rewardModelBuilder.hasStateRewards()) {
258 rewardModelBuilder.addStateReward(*stateRewardIt);
264 if (!generator->isDeterministicModel()) {
269 bool firstChoiceOfState =
true;
270 for (
auto const& choice : behavior) {
273 for (
auto const& label : choice.getLabels()) {
274 stateAndChoiceInformationBuilder.
addChoiceLabel(label, currentRow);
283 "There is a state where different players have an enabled choice.");
284 if (firstChoiceOfState) {
293 for (
auto const& stateProbabilityPair : choice) {
294 transitionMatrixBuilder.
addNextValue(currentRow, stateProbabilityPair.first, stateProbabilityPair.second);
298 auto choiceRewardIt = choice.getRewards().begin();
299 for (
auto& rewardModelBuilder : rewardModelBuilders) {
300 if (rewardModelBuilder.hasStateActionRewards()) {
301 rewardModelBuilder.addStateActionReward(*choiceRewardIt);
306 firstChoiceOfState =
false;
312 ++numberOfExploredStates;
313 if (generator->getOptions().isShowProgressSet()) {
314 ++numberOfExploredStatesSinceLastMessage;
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;
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.");
340 std::vector<uint_fast64_t>
const& remapping = stateRemapping.get();
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);
359 this->stateStorage.stateToId.remap([&remapping](StateType
const& state) {
return remapping[state]; });
361 this->generator->remapStateIds([&remapping](StateType
const& state) {
return remapping[state]; });
365template<
typename ValueType,
typename RewardModelType,
typename StateType>
369 bool deterministicModel = generator->isDeterministicModel();
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));
377 StateAndChoiceInformationBuilder stateAndChoiceInformationBuilder;
378 stateAndChoiceInformationBuilder.
setBuildChoiceLabels(generator->getOptions().isBuildChoiceLabelsSet());
379 stateAndChoiceInformationBuilder.setBuildChoiceOrigins(generator->getOptions().isBuildChoiceOriginsSet());
382 stateAndChoiceInformationBuilder.setBuildStateValuations(generator->getOptions().isBuildStateValuationsSet());
384 buildMatrices(transitionMatrixBuilder, rewardModelBuilders, stateAndChoiceInformationBuilder);
389 std::unordered_map<std::string, RewardModelType>(), !generator->isDiscreteTimeModel());
391 uint_fast64_t numStates = modelComponents.transitionMatrix.getColumnCount();
392 uint_fast64_t numChoices = modelComponents.transitionMatrix.getRowCount();
395 for (
auto& rewardModelBuilder : rewardModelBuilders) {
396 modelComponents.rewardModels.emplace(rewardModelBuilder.getName(),
397 rewardModelBuilder.build(numChoices, modelComponents.transitionMatrix.getColumnCount(), numStates));
400 if (stateAndChoiceInformationBuilder.isBuildStatePlayerIndications()) {
401 modelComponents.statePlayerIndications = stateAndChoiceInformationBuilder.buildStatePlayerIndications(numStates);
402 modelComponents.playerNameToIndexMap = generator->getPlayerNameToIndexMap();
405 if (stateAndChoiceInformationBuilder.isBuildMarkovianStates()) {
406 modelComponents.markovianStates = stateAndChoiceInformationBuilder.buildMarkovianStates(numStates);
409 if (stateAndChoiceInformationBuilder.isBuildChoiceLabels()) {
410 modelComponents.choiceLabeling = stateAndChoiceInformationBuilder.buildChoiceLabeling(numChoices);
413 if (stateAndChoiceInformationBuilder.isBuildStateValuations()) {
414 modelComponents.stateValuations = stateAndChoiceInformationBuilder.stateValuationsBuilder().build();
416 if (stateAndChoiceInformationBuilder.isBuildChoiceOrigins()) {
417 auto originData = stateAndChoiceInformationBuilder.buildDataOfChoiceOrigins(numChoices);
418 modelComponents.choiceOrigins = generator->generateChoiceOrigins(originData);
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;
428 modelComponents.observabilityClasses = classes;
429 if (generator->getOptions().isBuildObservationValuationsSet()) {
430 modelComponents.observationValuations = generator->makeObservationValuation();
433 return modelComponents;
436template<
typename ValueType,
typename RewardModelType,
typename StateType>
438 return generator->label(stateStorage, stateStorage.initialStateIndices, stateStorage.deadlockStateIndices, stateStorage.unexploredStateIndices);
442template class ExplicitModelBuilder<double, storm::models::sparse::StandardRewardModel<double>, uint32_t>;
443template class ExplicitStateLookup<uint32_t>;
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>;
448template class ExplicitModelBuilder<storm::Interval, storm::models::sparse::StandardRewardModel<storm::Interval>, uint32_t>;
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.
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.
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)
#define STORM_LOG_TRACE(message)
#define STORM_LOG_ASSERT(cond, message)
#define STORM_LOG_THROW(cond, exception, message)
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)
bool isTerminate()
Check whether the program should terminate (due to some abort signal).
Options()
Creates an object representing the default building options.
std::optional< StateType > explorationStateLimit
ExplorationOrder explorationOrder