Storm 1.10.0.1
A Modern Probabilistic Model Checker
Loading...
Searching...
No Matches
Scheduler.cpp
Go to the documentation of this file.
1
2#include <boost/algorithm/string/join.hpp>
3
10
11namespace storm {
12namespace storage {
13
14template<typename ValueType>
15Scheduler<ValueType>::Scheduler(uint_fast64_t numberOfModelStates, boost::optional<storm::storage::MemoryStructure> const& memoryStructure)
16 : memoryStructure(memoryStructure) {
17 uint_fast64_t numOfMemoryStates = memoryStructure ? memoryStructure->getNumberOfStates() : 1;
18 schedulerChoices = std::vector<std::vector<SchedulerChoice<ValueType>>>(numOfMemoryStates, std::vector<SchedulerChoice<ValueType>>(numberOfModelStates));
19 dontCareStates = std::vector<storm::storage::BitVector>(numOfMemoryStates, storm::storage::BitVector(numberOfModelStates, false));
20 numOfUndefinedChoices = numOfMemoryStates * numberOfModelStates;
21 numOfDeterministicChoices = 0;
22 numOfDontCareStates = 0;
23}
24
25template<typename ValueType>
26Scheduler<ValueType>::Scheduler(uint_fast64_t numberOfModelStates, boost::optional<storm::storage::MemoryStructure>&& memoryStructure)
27 : memoryStructure(std::move(memoryStructure)) {
28 uint_fast64_t numOfMemoryStates = this->memoryStructure ? this->memoryStructure->getNumberOfStates() : 1;
29 schedulerChoices = std::vector<std::vector<SchedulerChoice<ValueType>>>(numOfMemoryStates, std::vector<SchedulerChoice<ValueType>>(numberOfModelStates));
30 dontCareStates = std::vector<storm::storage::BitVector>(numOfMemoryStates, storm::storage::BitVector(numberOfModelStates, false));
31 numOfUndefinedChoices = numOfMemoryStates * numberOfModelStates;
32 numOfDeterministicChoices = 0;
33 numOfDontCareStates = 0;
34}
35
36template<typename ValueType>
37void Scheduler<ValueType>::setChoice(SchedulerChoice<ValueType> const& choice, uint_fast64_t modelState, uint_fast64_t memoryState) {
38 STORM_LOG_ASSERT(memoryState < getNumberOfMemoryStates(), "Illegal memory state index");
39 STORM_LOG_ASSERT(modelState < schedulerChoices[memoryState].size(), "Illegal model state index");
40
41 auto& schedulerChoice = schedulerChoices[memoryState][modelState];
42
43 if (schedulerChoice.isDefined()) {
44 if (!choice.isDefined()) {
45 ++numOfUndefinedChoices;
46 }
47 } else {
48 if (choice.isDefined()) {
49 assert(numOfUndefinedChoices > 0);
50 --numOfUndefinedChoices;
51 }
52 }
53 if (schedulerChoice.isDeterministic()) {
54 if (!choice.isDeterministic()) {
55 assert(numOfDeterministicChoices > 0);
56 --numOfDeterministicChoices;
57 }
58 } else {
59 if (choice.isDeterministic()) {
60 ++numOfDeterministicChoices;
61 }
62 }
63
64 schedulerChoice = choice;
65}
66
67template<typename ValueType>
68bool Scheduler<ValueType>::isChoiceSelected(BitVector const& selectedStates, uint64_t memoryState) const {
69 for (auto selectedState : selectedStates) {
70 auto& schedulerChoice = schedulerChoices[memoryState][selectedState];
71 if (!schedulerChoice.isDefined()) {
72 return false;
73 }
74 }
75 return true;
76}
77
78template<typename ValueType>
79void Scheduler<ValueType>::clearChoice(uint_fast64_t modelState, uint_fast64_t memoryState) {
80 STORM_LOG_ASSERT(memoryState < getNumberOfMemoryStates(), "Illegal memory state index");
81 STORM_LOG_ASSERT(modelState < schedulerChoices[memoryState].size(), "Illegal model state index");
82 setChoice(SchedulerChoice<ValueType>(), modelState, memoryState);
83}
84
85template<typename ValueType>
86SchedulerChoice<ValueType> const& Scheduler<ValueType>::getChoice(uint_fast64_t modelState, uint_fast64_t memoryState) const {
87 STORM_LOG_ASSERT(memoryState < getNumberOfMemoryStates(), "Illegal memory state index");
88 STORM_LOG_ASSERT(modelState < schedulerChoices[memoryState].size(), "Illegal model state index");
89 return schedulerChoices[memoryState][modelState];
90}
91
92template<typename ValueType>
93void Scheduler<ValueType>::setDontCare(uint_fast64_t modelState, uint_fast64_t memoryState, bool setArbitraryChoice) {
94 STORM_LOG_ASSERT(memoryState < getNumberOfMemoryStates(), "Illegal memory state index");
95 STORM_LOG_ASSERT(modelState < schedulerChoices[memoryState].size(), "Illegal model state index");
96
97 if (!dontCareStates[memoryState].get(modelState)) {
98 auto& schedulerChoice = schedulerChoices[memoryState][modelState];
99 if (!schedulerChoice.isDefined() && setArbitraryChoice) {
100 // Set an arbitrary choice
101 this->setChoice(0, modelState, memoryState);
102 }
103 dontCareStates[memoryState].set(modelState, true);
104 ++numOfDontCareStates;
105 }
106}
107
108template<typename ValueType>
109void Scheduler<ValueType>::unSetDontCare(uint_fast64_t modelState, uint_fast64_t memoryState) {
110 STORM_LOG_ASSERT(memoryState < getNumberOfMemoryStates(), "Illegal memory state index");
111 STORM_LOG_ASSERT(modelState < schedulerChoices[memoryState].size(), "Illegal model state index");
112
113 if (dontCareStates[memoryState].get(modelState)) {
114 dontCareStates[memoryState].set(modelState, false);
115 --numOfDontCareStates;
116 }
117}
118
119template<typename ValueType>
120bool Scheduler<ValueType>::isDontCare(uint_fast64_t modelState, uint64_t memoryState) const {
121 return dontCareStates[memoryState].get(modelState);
122}
123
124template<typename ValueType>
125storm::storage::BitVector Scheduler<ValueType>::computeActionSupport(std::vector<uint_fast64_t> const& nondeterministicChoiceIndices) const {
126 auto nrActions = nondeterministicChoiceIndices.back();
127 storm::storage::BitVector result(nrActions);
128
129 for (auto const& choicesPerMemoryNode : schedulerChoices) {
130 STORM_LOG_ASSERT(nondeterministicChoiceIndices.size() - 2 < choicesPerMemoryNode.size(), "Illegal model state index");
131 for (uint64_t stateId = 0; stateId < nondeterministicChoiceIndices.size() - 1; ++stateId) {
132 for (auto const& schedChoice : choicesPerMemoryNode[stateId].getChoiceAsDistribution()) {
133 STORM_LOG_ASSERT(schedChoice.first < nondeterministicChoiceIndices[stateId + 1] - nondeterministicChoiceIndices[stateId],
134 "Scheduler chooses action indexed " << schedChoice.first << " in state id " << stateId << " but state contains only "
135 << nondeterministicChoiceIndices[stateId + 1] - nondeterministicChoiceIndices[stateId]
136 << " choices .");
137 result.set(nondeterministicChoiceIndices[stateId] + schedChoice.first);
138 }
139 }
140 }
141 return result;
142}
143
144template<typename ValueType>
146 return numOfUndefinedChoices != 0;
147}
148
149template<typename ValueType>
151 return numOfDeterministicChoices == (schedulerChoices.size() * schedulerChoices.begin()->size()) - numOfUndefinedChoices;
152}
153
154template<typename ValueType>
156 return getNumberOfMemoryStates() == 1;
157}
158
159template<typename ValueType>
161 return memoryStructure ? memoryStructure->getNumberOfStates() : 1;
162}
163
164template<typename ValueType>
166 return schedulerChoices.empty() ? 0 : schedulerChoices.front().size();
167}
168
169template<typename ValueType>
170boost::optional<storm::storage::MemoryStructure> const& Scheduler<ValueType>::getMemoryStructure() const {
171 return memoryStructure;
172}
173
174template<typename ValueType>
175void Scheduler<ValueType>::printToStream(std::ostream& out, std::shared_ptr<storm::models::sparse::Model<ValueType>> model, bool skipUniqueChoices,
176 bool skipDontCareStates) const {
177 STORM_LOG_THROW(model == nullptr || model->getNumberOfStates() == schedulerChoices.front().size(), storm::exceptions::InvalidOperationException,
178 "The given model is not compatible with this scheduler.");
179
180 bool const stateValuationsGiven = model != nullptr && model->hasStateValuations();
181 bool const choiceLabelsGiven = model != nullptr && model->hasChoiceLabeling();
182 bool const choiceOriginsGiven = model != nullptr && model->hasChoiceOrigins();
183 uint_fast64_t widthOfStates = std::to_string(schedulerChoices.front().size()).length();
184 if (stateValuationsGiven) {
185 widthOfStates += model->getStateValuations().getStateInfo(schedulerChoices.front().size() - 1).length() + 5;
186 }
187 widthOfStates = std::max(widthOfStates, (uint_fast64_t)12);
188 uint_fast64_t numOfSkippedStatesWithUniqueChoice = 0;
189
190 out << "___________________________________________________________________\n";
191 out << (isPartialScheduler() ? "Partially" : "Fully") << " defined ";
192 out << (isMemorylessScheduler() ? "memoryless " : "");
193 out << (isDeterministicScheduler() ? "deterministic" : "randomized") << " scheduler";
194 if (!isMemorylessScheduler()) {
195 out << " with " << getNumberOfMemoryStates() << " memory states";
196 }
197 out << ":\n";
198 STORM_LOG_WARN_COND(!(skipUniqueChoices && model == nullptr), "Can not skip unique choices if the model is not given.");
199 out << std::setw(widthOfStates) << "model state:" << " " << (isMemorylessScheduler() ? "" : " memory: ") << "choice(s)"
200 << (isMemorylessScheduler() ? "" : " memory updates: ") << '\n';
201 for (uint_fast64_t state = 0; state < schedulerChoices.front().size(); ++state) {
202 // Check whether the state is skipped
203 if (skipUniqueChoices && model != nullptr && model->getTransitionMatrix().getRowGroupSize(state) == 1) {
204 ++numOfSkippedStatesWithUniqueChoice;
205 continue;
206 }
207
208 // Print the state info
209 if (stateValuationsGiven) {
210 out << std::setw(widthOfStates) << (std::to_string(state) + ": " + model->getStateValuations().getStateInfo(state));
211 } else {
212 out << std::setw(widthOfStates) << state;
213 }
214 out << " ";
215
216 bool firstMemoryState = true;
217 for (uint_fast64_t memoryState = 0; memoryState < getNumberOfMemoryStates(); ++memoryState) {
218 // Ignore dontCare states
219 if (skipDontCareStates && isDontCare(state, memoryState)) {
220 continue;
221 }
222
223 // Indent if this is not the first memory state
224 if (firstMemoryState) {
225 firstMemoryState = false;
226 } else {
227 out << std::setw(widthOfStates) << "";
228 out << " ";
229 }
230 // Print the memory state info
231 if (!isMemorylessScheduler()) {
232 out << "m=" << memoryState << std::setw(8) << "";
233 }
234
235 // Print choice info
236 SchedulerChoice<ValueType> const& choice = schedulerChoices[memoryState][state];
237 if (choice.isDefined()) {
238 if (choice.isDeterministic()) {
239 if (choiceOriginsGiven) {
240 out << model->getChoiceOrigins()->getChoiceInfo(model->getTransitionMatrix().getRowGroupIndices()[state] +
241 choice.getDeterministicChoice());
242 } else {
243 out << choice.getDeterministicChoice();
244 }
245 if (choiceLabelsGiven) {
246 auto choiceLabels = model->getChoiceLabeling().getLabelsOfChoice(model->getTransitionMatrix().getRowGroupIndices()[state] +
247 choice.getDeterministicChoice());
248 out << " {" << boost::join(choiceLabels, ", ") << "}";
249 }
250 } else {
251 bool firstChoice = true;
252 for (auto const& choiceProbPair : choice.getChoiceAsDistribution()) {
253 if (firstChoice) {
254 firstChoice = false;
255 } else {
256 out << " + ";
257 }
258 out << choiceProbPair.second << ": (";
259 if (choiceOriginsGiven) {
260 out << model->getChoiceOrigins()->getChoiceInfo(model->getTransitionMatrix().getRowGroupIndices()[state] + choiceProbPair.first);
261 } else {
262 out << choiceProbPair.first;
263 }
264 if (choiceLabelsGiven) {
265 auto choiceLabels = model->getChoiceLabeling().getLabelsOfChoice(model->getTransitionMatrix().getRowGroupIndices()[state] +
266 choice.getDeterministicChoice());
267 out << " {" << boost::join(choiceLabels, ", ") << "}";
268 }
269 out << ")";
270 }
271 }
272 } else {
273 out << "undefined.";
274 }
275
276 // Print memory updates
277 if (!isMemorylessScheduler()) {
278 STORM_LOG_THROW(model != nullptr, storm::exceptions::InvalidOperationException,
279 "Schedulers with memory can only be printed when the model is passed.");
280 out << std::setw(widthOfStates) << "";
281 // The memory updates do not depend on the actual choice, they only depend on the current model- and memory state as well as the successor model
282 // state.
283 for (auto const& choiceProbPair : choice.getChoiceAsDistribution()) {
284 uint64_t row = model->getTransitionMatrix().getRowGroupIndices()[state] + choiceProbPair.first;
285 bool firstUpdate = true;
286 for (auto entryIt = model->getTransitionMatrix().getRow(row).begin(); entryIt < model->getTransitionMatrix().getRow(row).end(); ++entryIt) {
287 if (firstUpdate) {
288 firstUpdate = false;
289 } else {
290 out << ", ";
291 }
292 out << "model state' = " << entryIt->getColumn() << ": -> "
293 << "(m' = " << this->memoryStructure->getSuccessorMemoryState(memoryState, entryIt - model->getTransitionMatrix().begin()) << ")";
294 // out << "model state' = " << entryIt->getColumn() << ": (transition = " << entryIt - model->getTransitionMatrix().begin() << ") -> "
295 // << "(m' = "<<this->memoryStructure->getSuccessorMemoryState(memoryState, entryIt - model->getTransitionMatrix().begin()) <<")";
296 }
297 }
298 }
299
300 out << '\n';
301 }
302 }
303 if (numOfSkippedStatesWithUniqueChoice > 0) {
304 out << "Skipped " << numOfSkippedStatesWithUniqueChoice << " deterministic states with unique choice.\n";
305 }
306 out << "___________________________________________________________________\n";
307}
308
309template<typename ValueType>
310void Scheduler<ValueType>::printJsonToStream(std::ostream& out, std::shared_ptr<storm::models::sparse::Model<ValueType>> model, bool skipUniqueChoices,
311 bool skipDontCareStates) const {
312 STORM_LOG_THROW(model == nullptr || model->getNumberOfStates() == schedulerChoices.front().size(), storm::exceptions::InvalidOperationException,
313 "The given model is not compatible with this scheduler.");
314 STORM_LOG_WARN_COND(!(skipUniqueChoices && model == nullptr), "Can not skip unique choices if the model is not given.");
316 for (uint64_t state = 0; state < schedulerChoices.front().size(); ++state) {
317 // Check whether the state is skipped
318 if (skipUniqueChoices && model != nullptr && model->getTransitionMatrix().getRowGroupSize(state) == 1) {
319 continue;
320 }
321
322 for (uint_fast64_t memoryState = 0; memoryState < getNumberOfMemoryStates(); ++memoryState) {
323 // Ignore dontCare states
324 if (skipDontCareStates && isDontCare(state, memoryState)) {
325 continue;
326 }
327
328 storm::json<storm::RationalNumber> stateChoicesJson;
329 if (model && model->hasStateValuations()) {
330 stateChoicesJson["s"] = model->getStateValuations().template toJson<storm::RationalNumber>(state);
331 } else {
332 stateChoicesJson["s"] = state;
333 }
334
335 if (!isMemorylessScheduler()) {
336 stateChoicesJson["m"] = memoryState;
337 }
338
339 auto const& choice = schedulerChoices[memoryState][state];
341 if (choice.isDefined()) {
342 for (auto const& choiceProbPair : choice.getChoiceAsDistribution()) {
343 uint64_t globalChoiceIndex = model->getTransitionMatrix().getRowGroupIndices()[state] + choiceProbPair.first;
345 if (model && model->hasChoiceOrigins() &&
346 model->getChoiceOrigins()->getIdentifier(globalChoiceIndex) != model->getChoiceOrigins()->getIdentifierForChoicesWithNoOrigin()) {
347 choiceJson["origin"] = model->getChoiceOrigins()->getChoiceAsJson(globalChoiceIndex);
348 }
349 if (model && model->hasChoiceLabeling()) {
350 auto choiceLabels = model->getChoiceLabeling().getLabelsOfChoice(globalChoiceIndex);
351 choiceJson["labels"] = std::vector<std::string>(choiceLabels.begin(), choiceLabels.end());
352 }
353 choiceJson["index"] = globalChoiceIndex;
354 choiceJson["prob"] = storm::utility::convertNumber<storm::RationalNumber>(choiceProbPair.second);
355
356 // Memory updates
357 if (!isMemorylessScheduler()) {
358 STORM_LOG_THROW(model != nullptr, storm::exceptions::InvalidOperationException,
359 "Schedulers with memory can only be printed when the model is passed.");
360 choiceJson["memory-updates"] = std::vector<storm::json<storm::RationalNumber>>();
361 uint64_t row = model->getTransitionMatrix().getRowGroupIndices()[state] + choiceProbPair.first;
362 for (auto entryIt = model->getTransitionMatrix().getRow(row).begin(); entryIt < model->getTransitionMatrix().getRow(row).end();
363 ++entryIt) {
365 // next model state
366 if (model && model->hasStateValuations()) {
367 updateJson["s'"] = model->getStateValuations().template toJson<storm::RationalNumber>(entryIt->getColumn());
368 } else {
369 updateJson["s'"] = entryIt->getColumn();
370 }
371 // next memory state
372 updateJson["m'"] = this->memoryStructure->getSuccessorMemoryState(memoryState, entryIt - model->getTransitionMatrix().begin());
373 choiceJson["memory-updates"].push_back(std::move(updateJson));
374 }
375 }
376
377 choicesJson.push_back(std::move(choiceJson));
378 }
379 } else {
380 choicesJson = "undefined";
381 }
382 stateChoicesJson["c"] = std::move(choicesJson);
383 output.push_back(std::move(stateChoicesJson));
384 }
385 }
386 out << storm::dumpJson(output);
387}
388
389template class Scheduler<double>;
392template class Scheduler<storm::Interval>;
393
394} // namespace storage
395} // namespace storm
Base class for all sparse models.
Definition Model.h:32
A bit vector that is internally represented as a vector of 64-bit values.
Definition BitVector.h:16
bool empty() const
Retrieves whether no bits are set to true in this bit vector.
void set(uint64_t index, bool value=true)
Sets the given truth value at the given index.
uint_fast64_t getDeterministicChoice() const
If this choice is deterministic, this function returns the selected (local) choice index.
storm::storage::Distribution< ValueType, uint_fast64_t > const & getChoiceAsDistribution() const
Retrieves this choice in the form of a probability distribution.
bool isDeterministic() const
Returns true iff this scheduler choice is deterministic (i.e., not randomized)
bool isDefined() const
Returns true iff this scheduler choice is defined.
This class defines which action is chosen in a particular state of a non-deterministic model.
Definition Scheduler.h:18
bool isDeterministicScheduler() const
Retrieves whether all defined choices are deterministic.
storm::storage::BitVector computeActionSupport(std::vector< uint64_t > const &nondeterministicChoiceIndicies) const
Compute the Action Support: A bit vector that indicates all actions that are selected with positive p...
void unSetDontCare(uint_fast64_t modelState, uint_fast64_t memoryState=0)
Unset the combination of model state and memoryStructure state to dontCare.
bool isPartialScheduler() const
Retrieves whether there is a reachable pair of model and memory state for which the choice is undefin...
uint_fast64_t getNumberOfModelStates() const
Retrieves the number of model states this scheduler considers.
SchedulerChoice< ValueType > const & getChoice(uint_fast64_t modelState, uint_fast64_t memoryState=0) const
Gets the choice defined by the scheduler for the given model and memory state.
Definition Scheduler.cpp:86
void clearChoice(uint_fast64_t modelState, uint_fast64_t memoryState=0)
Clears the choice defined by the scheduler for the given state.
Definition Scheduler.cpp:79
bool isDontCare(uint_fast64_t modelState, uint64_t memoryState=0) const
Is the combination of model state and memoryStructure state to reachable?
void setChoice(SchedulerChoice< ValueType > const &choice, uint_fast64_t modelState, uint_fast64_t memoryState=0)
Sets the choice defined by the scheduler for the given state.
Definition Scheduler.cpp:37
void printJsonToStream(std::ostream &out, std::shared_ptr< storm::models::sparse::Model< ValueType > > model=nullptr, bool skipUniqueChoices=false, bool skipDontCareStates=false) const
Prints the scheduler in json format to the given output stream.
boost::optional< storm::storage::MemoryStructure > const & getMemoryStructure() const
Retrieves the memory structure associated with this scheduler.
uint_fast64_t getNumberOfMemoryStates() const
Retrieves the number of memory states this scheduler considers.
void printToStream(std::ostream &out, std::shared_ptr< storm::models::sparse::Model< ValueType > > model=nullptr, bool skipUniqueChoices=false, bool skipDontCareStates=false) const
Prints the scheduler to the given output stream.
Scheduler(uint_fast64_t numberOfModelStates, boost::optional< storm::storage::MemoryStructure > const &memoryStructure=boost::none)
Initializes a scheduler for the given number of model states.
Definition Scheduler.cpp:15
void setDontCare(uint_fast64_t modelState, uint_fast64_t memoryState=0, bool setArbitraryChoice=true)
Set the combination of model state and memoryStructure state to dontCare.
Definition Scheduler.cpp:93
bool isChoiceSelected(BitVector const &selectedStates, uint64_t memoryState=0) const
Is the scheduler defined on the states indicated by the selected-states bitvector?
Definition Scheduler.cpp:68
bool isMemorylessScheduler() const
Retrieves whether the scheduler considers a trivial memory structure (i.e., a memory structure with j...
#define STORM_LOG_ASSERT(cond, message)
Definition macros.h:11
#define STORM_LOG_WARN_COND(cond, message)
Definition macros.h:38
#define STORM_LOG_THROW(cond, exception, message)
Definition macros.h:30
LabParser.cpp.
nlohmann::basic_json< std::map, std::vector, std::string, bool, int64_t, uint64_t, ValueType > json
Definition JsonForward.h:10
std::string dumpJson(storm::json< ValueType > const &j, bool compact)
Dumps the given json object, producing a String.