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
27namespace 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 */
78std::vector<AStarState *>
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. */
95AStar::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 */
133std::vector<AStarState *>
134AStar::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 size_t key()=0
Generates a unique key for this state.
virtual std::vector< AStarState * > children()=0
Generate all successors and put them to this vector.
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.