Fawkes API  Fawkes Development Version
astar.cpp
1 
2 /***************************************************************************
3  * astar.cpp - Implementation of A*
4  *
5  * Created: Mon Sep 15 18:38:00 2002
6  * Copyright 2007 Martin Liebenberg
7  * 2002 Stefan Jacobs
8  * 2012 Tim Niemueller [www.niemueller.de]
9  ****************************************************************************/
10 
11 /* This program is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version. A runtime exception applies to
15  * this software (see LICENSE.GPL_WRE file mentioned below for details).
16  *
17  * This program is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20  * GNU Library General Public License for more details.
21  *
22  * Read the full text in the LICENSE.GPL_WRE file in the doc directory.
23  */
24 
25 #include <utils/search/astar.h>
26 
27 namespace fawkes {
28 
29 /** @class AStar <utils/search/astar.h>
30  * This is an implementation of the A* search algorithm.
31  *
32  * @author Stefan Jacobs, Martin Liebenberg
33  */
34 /** @var AStar::closed_list
35  * This is AStars closed_list.
36  */
37 /** @var AStar::solution
38  * This is the final solution vector.
39  */
40 /** @var AStar::open_list
41  * This is AStars openlist.
42  */
43 /** @struct AStar::CmpSearchStateCost <utils/search/astar.h>
44  * Comparison structure to be used for the ordering on AStar::openList.
45  * @fn AStar::CmpSearchStateCost::operator() ( AStarState * a1, AStarState * a2 ) const
46  * The relation >= of this ordering.
47  * @param a1 the left operand
48  * @param a2 the right operand
49  * @return true, if a1 <= b1, else false
50  */
51 
52 /** Constructor.
53  * This is the constructor for the AStar Object.
54  */
56 {
57 }
58 
59 /** Destructor.
60  * This destructs the AStarObject.
61  */
63 {
64  AStarState *best = 0;
65  while (!open_list.empty()) {
66  best = open_list.top();
67  open_list.pop();
68  delete best;
69  }
70  closed_list.clear();
71 }
72 
73 /** Solves a situation given by the initial state with AStar, and
74  * returns a vector of AStarStates that solve the problem.
75  * @param initialState pointer of AStarState to the initial state
76  * @return a vector of pointers of AStarState with the solution sequence
77  */
78 std::vector<AStarState *>
79 AStar::solve(AStarState *initialState)
80 {
81  AStarState *best = 0;
82  while (open_list.size() > 0) {
83  best = open_list.top();
84  open_list.pop();
85  delete best;
86  }
87  closed_list.clear();
88 
89  open_list.push(initialState);
90  return solution_sequence(search());
91 }
92 
93 /** Search with astar. */
94 AStarState *
95 AStar::search()
96 {
97  AStarState * best = 0;
98  long key = 0;
99  std::vector<AStarState *> children;
100 
101  // while the openlist not is empty
102  while (open_list.size() > 0) {
103  // take the best state, and check if it is on closed list
104  do {
105  if (open_list.size() > 0) {
106  best = open_list.top();
107  open_list.pop();
108  } else
109  return 0;
110  key = best->key();
111  } while (closed_list.find(key) != closed_list.end());
112 
113  // put best state on closed list
114  closed_list[key] = best;
115 
116  // check if its a goal.
117  if (best->is_goal()) {
118  return best;
119  }
120  // generate all its children
121  children = best->children();
122  for (unsigned int i = 0; i < children.size(); i++)
123  open_list.push(children[i]);
124  }
125  return 0;
126 }
127 
128 /** Generates a solution sequence for a given state
129  * Initial solution is in solution[0]!
130  * @param node a pointer of AStarState to the goal
131  * @return the path from solution to initial solution
132  */
133 std::vector<AStarState *>
134 AStar::solution_sequence(AStarState *node)
135 {
136  solution.clear();
137  AStarState *state = node;
138 
139  while (state != 0) {
140  closed_list.erase(state->key());
141  solution.insert(solution.begin(), state);
142  state = state->parent;
143  }
144 
145  //delete the states, which are not part of the solution
146  while (closed_list.size() > 0) {
147  state = closed_list.begin()->second;
148  closed_list.erase(state->key());
149  delete state;
150  }
151  return solution;
152 }
153 
154 } // end namespace fawkes
This is the abstract(!) class for an A* State.
Definition: astar_state.h:39
virtual std::vector< AStarState * > children()=0
Generate all successors and put them to this vector.
virtual size_t key()=0
Generates a unique key for this state.
virtual bool is_goal()=0
Check, wether we reached a goal or not.
~AStar()
Destructor.
Definition: astar.cpp:62
std::vector< AStarState * > solve(AStarState *initialState)
Solves a situation given by the initial state with AStar, and returns a vector of AStarStates that so...
Definition: astar.cpp:79
AStar()
Constructor.
Definition: astar.cpp:55
This class tries to translate the found plan to interpreteable data for the rest of the program.
Fawkes library namespace.