Loading...
Searching...
No Matches
ProductGraph.h
1/*********************************************************************
2* Software License Agreement (BSD License)
3*
4* Copyright (c) 2012, Rice University
5* All rights reserved.
6*
7* Redistribution and use in source and binary forms, with or without
8* modification, are permitted provided that the following conditions
9* are met:
10*
11* * Redistributions of source code must retain the above copyright
12* notice, this list of conditions and the following disclaimer.
13* * Redistributions in binary form must reproduce the above
14* copyright notice, this list of conditions and the following
15* disclaimer in the documentation and/or other materials provided
16* with the distribution.
17* * Neither the name of the Rice University nor the names of its
18* contributors may be used to endorse or promote products derived
19* from this software without specific prior written permission.
20*
21* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32* POSSIBILITY OF SUCH DAMAGE.
33*********************************************************************/
34
35/* Author: Matt Maly */
36
37#ifndef OMPL_CONTROL_PLANNERS_LTL_PRODUCTGRAPH_
38#define OMPL_CONTROL_PLANNERS_LTL_PRODUCTGRAPH_
39
40#include "ompl/base/State.h"
41#include "ompl/control/planners/ltl/Automaton.h"
42#include "ompl/control/planners/ltl/PropositionalDecomposition.h"
43#include "ompl/util/ClassForward.h"
44#include <boost/graph/adjacency_list.hpp>
45#include <unordered_map>
46#include <map>
47#include <ostream>
48#include <vector>
49
50namespace ompl
51{
52 namespace control
53 {
55
56 OMPL_CLASS_FORWARD(ProductGraph);
58
67 {
68 public:
69 class State;
70
72
73 struct HashState
74 {
75 std::size_t operator()(const State &s) const;
76 };
78
83 class State
84 {
85 friend class ProductGraph;
86
87 public:
90 State() = default;
91
93 State(const State &s) = default;
94
98 bool operator==(const State &s) const;
99
103 bool isValid() const;
104
105 friend struct HashState;
106
108 friend std::ostream &operator<<(std::ostream &out, const State &s);
109
111 int getDecompRegion() const;
112
114 int getCosafeState() const;
115
117 int getSafeState() const;
118
119 private:
120 int decompRegion{-1};
121 int cosafeState{-1};
122 int safeState{-1};
123 };
124
127 ProductGraph(PropositionalDecompositionPtr decomp, AutomatonPtr cosafetyAut, AutomatonPtr safetyAut);
128
132 ProductGraph(const PropositionalDecompositionPtr &decomp, AutomatonPtr cosafetyAut);
133
134 ~ProductGraph();
135
139
142 const AutomatonPtr &getCosafetyAutom() const;
143
146 const AutomatonPtr &getSafetyAutom() const;
147
156 std::vector<State *> computeLead(State *start, const std::function<double(State *, State *)> &edgeWeight);
157
159 void clear();
160
166 void buildGraph(State *start, const std::function<void(State *)> &initialize = [](State *){});
167
174 bool isSolution(const State *s) const;
175
177 State *getStartState() const;
178
181 double getRegionVolume(const State *s);
182
185 int getCosafeAutDistance(const State *s) const;
186
189 int getSafeAutDistance(const State *s) const;
190
194 State *getState(const base::State *cs) const;
195
199 State *getState(const base::State *cs, int cosafe, int safe) const;
200
204 State *getState(const State *parent, int nextRegion) const;
205
210 State *getState(const State *parent, const base::State *cs) const;
211
214 State *getState(int region, int cosafe, int safe) const
215 {
216 State s;
217 s.decompRegion = region;
218 s.cosafeState = cosafe;
219 s.safeState = safe;
220 State *&ret = stateToPtr_[s];
221 if (ret == nullptr)
222 ret = new State(s);
223 return ret;
224 }
225
226 protected:
227 struct Edge
228 {
229 double cost;
230 };
231
232 using GraphType = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, State *, Edge>;
233 using Vertex = boost::graph_traits<GraphType>::vertex_descriptor;
234 using VertexIter = boost::graph_traits<GraphType>::vertex_iterator;
235 using VertexIndexMap = boost::property_map<GraphType, boost::vertex_index_t>::type;
236 using EdgeIter = boost::graph_traits<GraphType>::edge_iterator;
237
239 AutomatonPtr cosafety_;
240 AutomatonPtr safety_;
241 GraphType graph_;
242 State *startState_;
243 std::vector<State *> solutionStates_;
244
245 /* Only one State pointer will be allocated for each possible State
246 in the ProductGraph. There will exist situations in which
247 all we have are the component values (region, automaton states)
248 of a State and we want the actual State pointer.
249 We use this map to access it. */
250 mutable std::unordered_map<State, State *, HashState> stateToPtr_;
251
252 /* Map from State pointer to the index of the corresponding vertex
253 in the graph. */
254 std::unordered_map<State *, int> stateToIndex_;
255 };
256 }
257}
258#endif
A shared pointer wrapper for ompl::control::Automaton.
A State of a ProductGraph represents a vertex in the graph-based Cartesian product represented by the...
int getDecompRegion() const
Returns this State's PropositionalDecomposition region component.
bool operator==(const State &s) const
Returns whether this State is equivalent to a given State, by comparing their PropositionalDecomposit...
bool isValid() const
Returns whether this State is valid. A State is valid if and only if none of its Automaton states are...
int getCosafeState() const
Returns this State's co-safe Automaton state component.
friend std::ostream & operator<<(std::ostream &out, const State &s)
Helper function to print this State to a given output stream.
State(const State &s)=default
Basic copy constructor for State.
State()=default
Creates a State without any assigned PropositionalDecomposition region or Automaton states....
int getSafeState() const
Returns this State's safe Automaton state component.
A ProductGraph represents the weighted, directed, graph-based Cartesian product of a PropositionalDec...
bool isSolution(const State *s) const
Returns whether the given State is an accepting State in this ProductGraph. We call a State accepting...
State * getStartState() const
Returns the initial State of this ProductGraph.
State * getState(const base::State *cs) const
Returns a ProductGraph State with initial co-safety and safety Automaton states, and the Propositiona...
const PropositionalDecompositionPtr & getDecomp() const
Returns the PropositionalDecomposition contained within this ProductGraph.
int getSafeAutDistance(const State *s) const
Helper method to return the distance from a given State's safety state to an accepting state in the s...
State * getState(int region, int cosafe, int safe) const
Returns the ProductGraph state corresponding to the given region, co-safety state,...
std::vector< State * > computeLead(State *start, const std::function< double(State *, State *)> &edgeWeight)
Returns a shortest-path sequence of ProductGraph states, beginning with a given initial State and end...
void clear()
Clears all memory belonging to this ProductGraph.
const AutomatonPtr & getSafetyAutom() const
Returns the safe Automaton contained within this ProductGraph.
double getRegionVolume(const State *s)
Helper method to return the volume of the PropositionalDecomposition region corresponding to the give...
const AutomatonPtr & getCosafetyAutom() const
Returns the co-safe Automaton contained within this ProductGraph.
void buildGraph(State *start, const std::function< void(State *)> &initialize=[](State *){})
Constructs this ProductGraph beginning with a given initial State, using a breadth-first search....
int getCosafeAutDistance(const State *s) const
Helper method to return the distance from a given State's co-safety state to an accepting state in th...
A shared pointer wrapper for ompl::control::PropositionalDecomposition.
Main namespace. Contains everything in this library.