| 1 | package dk.deepthought.sidious.planner.graph; |
| 2 | |
| 3 | import java.util.ArrayList; |
| 4 | import java.util.Collection; |
| 5 | import java.util.List; |
| 6 | |
| 7 | import org.apache.commons.logging.Log; |
| 8 | import org.apache.commons.logging.LogFactory; |
| 9 | |
| 10 | import dk.deepthought.sidious.planner.Heuristic; |
| 11 | import dk.deepthought.sidious.ruleengine.RuleEngine; |
| 12 | import dk.deepthought.sidious.supportsystem.Adjustable; |
| 13 | import dk.deepthought.sidious.supportsystem.Repository; |
| 14 | import dk.deepthought.sidious.supportsystem.State; |
| 15 | import dk.deepthought.sidious.supportsystem.Step; |
| 16 | import dk.deepthought.sidious.supportsystem.SuperLinkID; |
| 17 | |
| 18 | /** |
| 19 | * Represents a graph for use with the A-Star algorithm. |
| 20 | * @author Deepthought |
| 21 | * |
| 22 | */ |
| 23 | public final class AStarGraph implements Graph { |
| 24 | |
| 25 | /** |
| 26 | * The logger of this class. |
| 27 | */ |
| 28 | private static final Log logger = LogFactory.getLog(AStarGraph.class); |
| 29 | |
| 30 | /** |
| 31 | * The vertices of this. |
| 32 | */ |
| 33 | private final List<Vertex> vertices; |
| 34 | |
| 35 | /** |
| 36 | * The source vertex of this. |
| 37 | */ |
| 38 | private final Vertex sourceVertex; |
| 39 | |
| 40 | /** |
| 41 | * The goal vertex of this. It can be substituted if an approximate goal is set. |
| 42 | */ |
| 43 | private Vertex goalVertex; |
| 44 | |
| 45 | /** |
| 46 | * The heuristic to be used with this. |
| 47 | */ |
| 48 | private final Heuristic heuristic; |
| 49 | |
| 50 | /** |
| 51 | * The id of the requester. |
| 52 | */ |
| 53 | private final SuperLinkID requesterId; |
| 54 | |
| 55 | /** |
| 56 | * Cached instance of the rule engine. |
| 57 | */ |
| 58 | private final RuleEngine ruleEngine; |
| 59 | |
| 60 | /** |
| 61 | * Constructs an <code>AStarGraph</code> with a start and end-state, and |
| 62 | * the set adjustables. |
| 63 | * |
| 64 | * @param sourceState |
| 65 | * the beginning state of any path |
| 66 | * @param goalState |
| 67 | * the end state of any path |
| 68 | * @param adjustables |
| 69 | * the adjustables of the current requester |
| 70 | * @param heuristic |
| 71 | * the heuristic of the graph |
| 72 | * @param requester |
| 73 | * the id of the plan requester |
| 74 | */ |
| 75 | public AStarGraph(State sourceState, State goalState, |
| 76 | Collection<Adjustable> adjustables, Heuristic heuristic, |
| 77 | SuperLinkID requester) { |
| 78 | this.heuristic = heuristic; |
| 79 | AStarVertex proxySource = new AStarVertex(sourceState, heuristic |
| 80 | .h(sourceState)); |
| 81 | AStarVertex proxyGoal = new AStarVertex(goalState, 0); |
| 82 | sourceVertex = proxySource.toSourceVertex(new Step(adjustables)); |
| 83 | goalVertex = proxyGoal.toGoalVertex(); |
| 84 | vertices = new ArrayList<Vertex>(); |
| 85 | vertices.add(goalVertex); |
| 86 | vertices.add(sourceVertex); |
| 87 | this.requesterId = requester; |
| 88 | ruleEngine = Repository.getRuleEngine(); |
| 89 | if (logger.isDebugEnabled()) { |
| 90 | logger.debug("AStarGraph(State sourceState=" + sourceState |
| 91 | + ", State goalState=" + goalState |
| 92 | + ", Collection<Adjustable> adjustables=" + adjustables |
| 93 | + ", Heuristic heuristic=" + heuristic |
| 94 | + ", SuperLinkID id=" + requester + ")"); |
| 95 | } |
| 96 | } |
| 97 | |
| 98 | /** |
| 99 | * This method retrieves the edges emanating from the <code>Vertex</code> |
| 100 | * v. It does this by calculating the edges and vertices on-the-fly. |
| 101 | * |
| 102 | * @see dk.deepthought.sidious.planner.graph.Graph#getEdges(dk.deepthought.sidious.planner.graph.Vertex) |
| 103 | */ |
| 104 | public Collection<Edge> getEdges(Vertex v) { |
| 105 | if (logger.isDebugEnabled()) { |
| 106 | logger.debug("getEdges(Vertex v=" + v + ") - start"); |
| 107 | } |
| 108 | if (v == null) { |
| 109 | String fail = "Input vertex can not be null"; |
| 110 | logger.error(fail); |
| 111 | throw new IllegalArgumentException(fail); |
| 112 | } |
| 113 | State oldState = v.getState(); |
| 114 | Step stepToHere = v.getStepToThis(); |
| 115 | Collection<Step> possibleNewSteps = stepToHere.getSteps(); |
| 116 | Collection<Edge> edgesForV = new ArrayList<Edge>(); |
| 117 | for (Step step : possibleNewSteps) { |
| 118 | State state = step.consequence(oldState); |
| 119 | Vertex newVertex = getVertexFromState(state); |
| 120 | double cost = calculateCost(oldState, state, step); |
| 121 | Edge newEdge = new AStarEdge(v, newVertex, step, cost); |
| 122 | edgesForV.add(newEdge); |
| 123 | } |
| 124 | |
| 125 | if (logger.isDebugEnabled()) { |
| 126 | logger.debug("getEdges(Vertex v=" + v + ") - end - return value=" |
| 127 | + edgesForV); |
| 128 | } |
| 129 | return edgesForV; |
| 130 | } |
| 131 | |
| 132 | /** |
| 133 | * Method returns the calculated cost of getting from <code>current</code> |
| 134 | * to <code>next</code>. |
| 135 | * |
| 136 | * @param current |
| 137 | * the current state |
| 138 | * @param next |
| 139 | * the next state |
| 140 | * @param step |
| 141 | * the step |
| 142 | * @return the cost |
| 143 | */ |
| 144 | double calculateCost(State current, State next, Step step) { |
| 145 | return ruleEngine.evaluate(requesterId, current, next, step); |
| 146 | } |
| 147 | |
| 148 | /** |
| 149 | * This method checks if the <code>state</code> is represented by a |
| 150 | * <code>Vertex</code> in the graph, and returns either the representing |
| 151 | * vertex or a new vertex, which is added to the graph. |
| 152 | * |
| 153 | * @param state |
| 154 | * the state |
| 155 | * @return the vertex representing the state |
| 156 | */ |
| 157 | synchronized Vertex getVertexFromState(State state) { |
| 158 | if (logger.isDebugEnabled()) { |
| 159 | logger.debug("getVertexFromState(State state=" + state |
| 160 | + ") - start"); |
| 161 | } |
| 162 | if (state == null) { |
| 163 | throw new IllegalArgumentException( |
| 164 | "Cannot create a Vertex from null"); |
| 165 | } |
| 166 | |
| 167 | AStarVertex newVertex = new AStarVertex(state, heuristic.h(state)); |
| 168 | int index = vertices.indexOf(newVertex); |
| 169 | if (index >= 0) { |
| 170 | Vertex returnVertex = vertices.get(index); |
| 171 | if (logger.isDebugEnabled()) { |
| 172 | logger.debug("getVertexFromState(State state=" + state |
| 173 | + ") - end - return value=" + returnVertex); |
| 174 | } |
| 175 | return returnVertex; |
| 176 | } else { |
| 177 | boolean success = vertices.add(newVertex); |
| 178 | if (!success) { |
| 179 | logger.error("Vertex " + newVertex |
| 180 | + " was not added to list of vertices"); |
| 181 | } |
| 182 | |
| 183 | if (logger.isDebugEnabled()) { |
| 184 | logger.debug("getVertexFromState(State state=" + state |
| 185 | + ") - end - return value=" + newVertex); |
| 186 | } |
| 187 | return newVertex; |
| 188 | } |
| 189 | } |
| 190 | |
| 191 | /* |
| 192 | * (non-Javadoc) |
| 193 | * |
| 194 | * @see dk.deepthought.sidious.planner.Graph#getGoalVertex() |
| 195 | */ |
| 196 | public Vertex getGoalVertex() { |
| 197 | return goalVertex; |
| 198 | } |
| 199 | |
| 200 | /* |
| 201 | * (non-Javadoc) |
| 202 | * |
| 203 | * @see dk.deepthought.sidious.planner.Graph#sourceVertex() |
| 204 | */ |
| 205 | public Vertex getSourceVertex() { |
| 206 | assert sourceVertex.g() == 0 : "g-value of sourceVertex not 0"; |
| 207 | assert sourceVertex.getPredecessorVertex() == null : "predecessor of sourceVertex not null"; |
| 208 | return sourceVertex; |
| 209 | } |
| 210 | |
| 211 | |
| 212 | /* (non-Javadoc) |
| 213 | * @see dk.deepthought.sidious.planner.graph.Graph#getId() |
| 214 | */ |
| 215 | public SuperLinkID getId() { |
| 216 | return requesterId; |
| 217 | } |
| 218 | |
| 219 | /* |
| 220 | * (non-Javadoc) |
| 221 | * |
| 222 | * @see java.lang.Object#toString() |
| 223 | */ |
| 224 | @Override |
| 225 | public String toString() { |
| 226 | return getClass().getSimpleName() + "[id=" + requesterId + ", source=" + sourceVertex + ", goal=" |
| 227 | + goalVertex + "]"; |
| 228 | } |
| 229 | |
| 230 | /* (non-Javadoc) |
| 231 | * @see dk.deepthought.sidious.planner.Graph#approximateGoal(dk.deepthought.sidious.planner.Vertex) |
| 232 | */ |
| 233 | public void setApproximateGoal(Vertex v) { |
| 234 | if(v.partiallyEquals(goalVertex)) { |
| 235 | goalVertex = v; |
| 236 | } else { |
| 237 | throw new IllegalArgumentException("Not a valid goal candidate!"); |
| 238 | } |
| 239 | } |
| 240 | } |