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 
53 /** Constructor.
54  * This is the constructor for the AStar Object.
55  */
57 {
58 }
59 
60 /** Destructor.
61  * This destructs the AStarObject.
62  */
64 {
65  AStarState * best = 0;
66  while ( ! open_list.empty() )
67  {
68  best = open_list.top();
69  open_list.pop();
70  delete best;
71  }
72  closed_list.clear();
73 }
74 
75 /** Solves a situation given by the initial state with AStar, and
76  * returns a vector of AStarStates that solve the problem.
77  * @param initialState pointer of AStarState to the initial state
78  * @return a vector of pointers of AStarState with the solution sequence
79  */
80 std::vector< AStarState * > AStar::solve( AStarState * initialState )
81 {
82  AStarState * best = 0;
83  while ( open_list.size() > 0 )
84  {
85  best = open_list.top();
86  open_list.pop();
87  delete best;
88  }
89  closed_list.clear();
90 
91  open_list.push( initialState );
92  return solution_sequence( search() );
93 }
94 
95 
96 /** Search with astar. */
97 AStarState * AStar::search( )
98 {
99  AStarState * best = 0;
100  long key = 0;
101  std::vector< AStarState * > children;
102 
103  // while the openlist not is empty
104  while ( open_list.size() > 0 )
105  {
106  // take the best state, and check if it is on closed list
107  do
108  {
109  if ( open_list.size() > 0 )
110  {
111  best = open_list.top();
112  open_list.pop( );
113  }
114  else
115  return 0;
116  key = best->key( );
117  }
118  while ( closed_list.find( key ) != closed_list.end() );
119 
120  // put best state on closed list
121  closed_list[key] = best;
122 
123  // check if its a goal.
124  if ( best->is_goal( ) )
125  {
126  return best;
127  }
128  // generate all its children
129  children = best->children( );
130  for ( unsigned int i = 0; i < children.size(); i++ )
131  open_list.push( children[i] );
132  }
133  return 0;
134 }
135 
136 
137 /** Generates a solution sequence for a given state
138  * Initial solution is in solution[0]!
139  * @param node a pointer of AStarState to the goal
140  * @return the path from solution to initial solution
141  */
142 std::vector<AStarState *>
143 AStar::solution_sequence(AStarState * node)
144 {
145  solution.clear();
146  AStarState * state = node;
147 
148  while ( state != 0 )
149  {
150  closed_list.erase(state->key());
151  solution.insert( solution.begin(), state );
152  state = state->parent;
153  }
154 
155  //delete the states, which are not part of the solution
156  while ( closed_list.size() > 0 )
157  {
158  state = closed_list.begin()->second;
159  closed_list.erase(state->key());
160  delete state;
161  }
162  return solution;
163 }
164 
165 
166 } // end namespace fawkes
This is the abstract(!) class for an A* State.
Definition: astar_state.h:38
AStarState * parent
Predecessor.
Definition: astar_state.h:79
virtual size_t key()=0
Generates a unique key for this state.
This class tries to translate the found plan to interpreteable data for the rest of the program...
Fawkes library namespace.
~AStar()
Destructor.
Definition: astar.cpp:63
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:80
virtual bool is_goal()=0
Check, wether we reached a goal or not.
virtual std::vector< AStarState * > children()=0
Generate all successors and put them to this vector.
AStar()
Constructor.
Definition: astar.cpp:56