SUMO - Simulation of Urban MObility
AStarRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
9 // A* Algorithm using euclidean distance heuristic.
10 // Based on DijkstraRouterTT. For routing by effort a novel heuristic would be needed.
11 /****************************************************************************/
12 // SUMO, Simulation of Urban MObility; see http://sumo.dlr.de/
13 // Copyright (C) 2012-2016 DLR (http://www.dlr.de/) and contributors
14 /****************************************************************************/
15 //
16 // This file is part of SUMO.
17 // SUMO is free software: you can redistribute it and/or modify
18 // it under the terms of the GNU General Public License as published by
19 // the Free Software Foundation, either version 3 of the License, or
20 // (at your option) any later version.
21 //
22 /****************************************************************************/
23 #ifndef AStarRouter_h
24 #define AStarRouter_h
25 
26 
27 // ===========================================================================
28 // included modules
29 // ===========================================================================
30 #ifdef _MSC_VER
31 #include <windows_config.h>
32 #else
33 #include <config.h>
34 #endif
35 
36 #include <cassert>
37 #include <string>
38 #include <functional>
39 #include <vector>
40 #include <set>
41 #include <limits>
42 #include <algorithm>
43 #include <iterator>
44 #include <map>
46 #include <utils/common/StdDefs.h>
47 #include <utils/common/ToString.h>
49 #include "SUMOAbstractRouter.h"
50 
51 
52 // ===========================================================================
53 // class definitions
54 // ===========================================================================
70 template<class E, class V, class PF>
71 class AStarRouter : public SUMOAbstractRouter<E, V>, public PF {
72 
73 public:
74  typedef SUMOReal(* Operation)(const E* const, const V* const, SUMOReal);
75  typedef std::vector<std::vector<SUMOReal> > LookupTable;
76 
82  class EdgeInfo {
83  public:
85  EdgeInfo(const E* e) :
86  edge(e),
87  traveltime(std::numeric_limits<SUMOReal>::max()),
88  heuristicTime(std::numeric_limits<SUMOReal>::max()),
89  prev(0),
90  visited(false) {
91  }
92 
94  const E* edge;
95 
98 
101 
104 
106  bool visited;
107 
108  inline void reset() {
109  // heuristicTime is set before adding to the frontier, thus no reset is needed
110  traveltime = std::numeric_limits<SUMOReal>::max();
111  visited = false;
112  }
113 
114  };
115 
121  public:
123  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
124  if (nod1->heuristicTime == nod2->heuristicTime) {
125  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
126  }
127  return nod1->heuristicTime > nod2->heuristicTime;
128  }
129  };
130 
132  AStarRouter(const std::vector<E*>& edges, bool unbuildIsWarning, Operation operation, const LookupTable* const lookup = 0):
133  SUMOAbstractRouter<E, V>(operation, "AStarRouter"),
134  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
135  myLookupTable(lookup) {
136  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
137  myEdgeInfos.push_back(EdgeInfo(*i));
138  }
139  }
140 
141  AStarRouter(const std::vector<EdgeInfo>& edgeInfos, bool unbuildIsWarning, Operation operation, const LookupTable* const lookup = 0):
142  SUMOAbstractRouter<E, V>(operation, "AStarRouter"),
143  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
144  myLookupTable(lookup) {
145  for (typename std::vector<EdgeInfo>::const_iterator i = edgeInfos.begin(); i != edgeInfos.end(); ++i) {
146  myEdgeInfos.push_back(*i);
147  }
148  }
149 
151  virtual ~AStarRouter() {}
152 
155  }
156 
157  static LookupTable* createLookupTable(const std::string& filename, const int size) {
158  LookupTable* const result = new LookupTable();
159  BinaryInputDevice dev(filename);
160  for (int i = 0; i < size; i++) {
161  for (int j = 0; j < size; j++) {
162  SUMOReal val;
163  dev >> val;
164  (*result)[i].push_back(val);
165  }
166  }
167  return result;
168  }
169 
170  void init() {
171  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
172  for (typename std::vector<EdgeInfo*>::iterator i = myFrontierList.begin(); i != myFrontierList.end(); i++) {
173  (*i)->reset();
174  }
175  myFrontierList.clear();
176  for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
177  (*i)->reset();
178  }
179  myFound.clear();
180  }
181 
182 
184  virtual bool compute(const E* from, const E* to, const V* const vehicle,
185  SUMOTime msTime, std::vector<const E*>& into) {
186  assert(from != 0 && to != 0);
187  // check whether from and to can be used
188  if (PF::operator()(from, vehicle)) {
189  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on source edge '" + from->getID() + "'.");
190  return false;
191  }
192  if (PF::operator()(to, vehicle)) {
193  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on destination edge '" + to->getID() + "'.");
194  return false;
195  }
196  this->startQuery();
197  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
198  const SUMOReal time = STEPS2TIME(msTime);
199  if (this->myBulkMode) {
200  const EdgeInfo& toInfo = myEdgeInfos[to->getNumericalID()];
201  if (toInfo.visited) {
202  buildPathFrom(&toInfo, into);
203  this->endQuery(1);
204  return true;
205  }
206  } else {
207  init();
208  // add begin node
209  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
210  fromInfo->traveltime = 0;
211  fromInfo->prev = 0;
212  myFrontierList.push_back(fromInfo);
213  }
214  // loop
215  int num_visited = 0;
216  while (!myFrontierList.empty()) {
217  num_visited += 1;
218  // use the node with the minimal length
219  EdgeInfo* const minimumInfo = myFrontierList.front();
220  const E* const minEdge = minimumInfo->edge;
221  // check whether the destination node was already reached
222  if (minEdge == to) {
223  buildPathFrom(minimumInfo, into);
224  this->endQuery(num_visited);
225  return true;
226  }
227  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
228  myFrontierList.pop_back();
229  myFound.push_back(minimumInfo);
230  minimumInfo->visited = true;
231  const SUMOReal traveltime = minimumInfo->traveltime + this->getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
232  // admissible A* heuristic: straight line distance at maximum speed
233  const SUMOReal heuristic_remaining = myLookupTable == 0 ? minEdge->getDistanceTo(to) / vehicle->getMaxSpeed() : (*myLookupTable)[minEdge->getNumericalID()][to->getNumericalID()] / vehicle->getChosenSpeedFactor();
234  // check all ways from the node with the minimal length
235  const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
236  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
237  const E* const follower = *it;
238  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
239  // check whether it can be used
240  if (PF::operator()(follower, vehicle)) {
241  continue;
242  }
243  const SUMOReal oldEffort = followerInfo->traveltime;
244  if (!followerInfo->visited && traveltime < oldEffort) {
245  followerInfo->traveltime = traveltime;
246  followerInfo->heuristicTime = traveltime + heuristic_remaining;
247  /* the code below results in fewer edges being looked up but is more costly due to the effort
248  calculations. Overall it resulted in a slowdown in the Berlin tests but could be made configurable someday.
249  followerInfo->heuristicTime = traveltime;
250  if (follower != to) {
251  if (myLookupTable == 0) {
252  // admissible A* heuristic: straight line distance at maximum speed
253  followerInfo->heuristicTime += this->getEffort(follower, vehicle, time + traveltime) + follower->getDistanceTo(to) / vehicle->getMaxSpeed();
254  } else {
255  followerInfo->heuristicTime += this->getEffort(follower, vehicle, time + traveltime) + (*myLookupTable)[follower->getNumericalID()][to->getNumericalID()] / vehicle->getChosenSpeedFactor();
256  }
257  }*/
258  followerInfo->prev = minimumInfo;
259  if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
260  myFrontierList.push_back(followerInfo);
261  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
262  } else {
263  push_heap(myFrontierList.begin(),
264  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
265  myComparator);
266  }
267  }
268  }
269  }
270  this->endQuery(num_visited);
271  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
272  return false;
273  }
274 
275 
276  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
277  const SUMOReal time = STEPS2TIME(msTime);
278  SUMOReal costs = 0;
279  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
280  if (PF::operator()(*i, v)) {
281  return -1;
282  }
283  costs += this->getEffort(*i, v, time + costs);
284  }
285  return costs;
286  }
287 
288 public:
290  void buildPathFrom(const EdgeInfo* rbegin, std::vector<const E*>& edges) {
291  std::vector<const E*> tmp;
292  while (rbegin != 0) {
293  tmp.push_back(rbegin->edge);
294  rbegin = rbegin->prev;
295  }
296  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
297  }
298 
299 protected:
301  std::vector<EdgeInfo> myEdgeInfos;
302 
304  std::vector<EdgeInfo*> myFrontierList;
306  std::vector<EdgeInfo*> myFound;
307 
308  EdgeInfoComparator myComparator;
309 
312 
314  const LookupTable* const myLookupTable;
315 };
316 
317 
318 #endif
319 
320 /****************************************************************************/
321 
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:71
SUMOReal recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
Definition: AStarRouter.h:276
static LookupTable * createLookupTable(const std::string &filename, const int size)
Definition: AStarRouter.h:157
long long int SUMOTime
Definition: SUMOTime.h:43
AStarRouter(const std::vector< EdgeInfo > &edgeInfos, bool unbuildIsWarning, Operation operation, const LookupTable *const lookup=0)
Definition: AStarRouter.h:141
bool visited
The previous edge.
Definition: AStarRouter.h:106
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
Definition: AStarRouter.h:301
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
Definition: AStarRouter.h:304
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E *> &into)
Builds the route between the given edges using the minimum travel time.
Definition: AStarRouter.h:184
EdgeInfoComparator myComparator
Definition: AStarRouter.h:308
std::vector< std::vector< SUMOReal > > LookupTable
Definition: AStarRouter.h:75
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: AStarRouter.h:311
Computes the shortest path through a network using the A* algorithm.
Definition: AStarRouter.h:71
AStarRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation operation, const LookupTable *const lookup=0)
Constructor.
Definition: AStarRouter.h:132
void init()
Definition: AStarRouter.h:170
EdgeInfo * prev
The previous edge.
Definition: AStarRouter.h:103
#define max(a, b)
Definition: polyfonts.c:65
virtual SUMOAbstractRouter< E, V > * clone()
Definition: AStarRouter.h:153
EdgeInfo(const E *e)
Constructor.
Definition: AStarRouter.h:85
virtual ~AStarRouter()
Destructor.
Definition: AStarRouter.h:151
bool myBulkMode
whether we are currently operating several route queries in a bulk
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
void buildPathFrom(const EdgeInfo *rbegin, std::vector< const E *> &edges)
Builds the path from marked edges.
Definition: AStarRouter.h:290
Operation myOperation
The object&#39;s operation to perform.
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
Definition: AStarRouter.h:123
SUMOReal heuristicTime
Estimated time to reach the edge (traveltime + lower bound on remaining time)
Definition: AStarRouter.h:100
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:89
#define SUMOReal
Definition: config.h:213
void endQuery(int visits)
const LookupTable *const myLookupTable
the lookup table for travel time heuristics
Definition: AStarRouter.h:314
SUMOReal traveltime
Effort to reach the edge.
Definition: AStarRouter.h:97
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
Definition: AStarRouter.h:306
Encapsulates binary reading operations on a file.
vehicles ignoring classes
SUMOReal(* Operation)(const E *const, const V *const, SUMOReal)
Definition: AStarRouter.h:74
const E * edge
The current edge.
Definition: AStarRouter.h:94