001 package dk.deepthought.sidious.planner.graph;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.List;
006
007 import org.apache.commons.logging.Log;
008 import org.apache.commons.logging.LogFactory;
009
010 import dk.deepthought.sidious.planner.Heuristic;
011 import dk.deepthought.sidious.ruleengine.RuleEngine;
012 import dk.deepthought.sidious.supportsystem.Adjustable;
013 import dk.deepthought.sidious.supportsystem.Repository;
014 import dk.deepthought.sidious.supportsystem.State;
015 import dk.deepthought.sidious.supportsystem.Step;
016 import dk.deepthought.sidious.supportsystem.SuperLinkID;
017
018 /**
019 * Represents a graph for use with the A-Star algorithm.
020 * @author Deepthought
021 *
022 */
023 public final class AStarGraph implements Graph {
024
025 /**
026 * The logger of this class.
027 */
028 private static final Log logger = LogFactory.getLog(AStarGraph.class);
029
030 /**
031 * The vertices of this.
032 */
033 private final List<Vertex> vertices;
034
035 /**
036 * The source vertex of this.
037 */
038 private final Vertex sourceVertex;
039
040 /**
041 * The goal vertex of this. It can be substituted if an approximate goal is set.
042 */
043 private Vertex goalVertex;
044
045 /**
046 * The heuristic to be used with this.
047 */
048 private final Heuristic heuristic;
049
050 /**
051 * The id of the requester.
052 */
053 private final SuperLinkID requesterId;
054
055 /**
056 * Cached instance of the rule engine.
057 */
058 private final RuleEngine ruleEngine;
059
060 /**
061 * Constructs an <code>AStarGraph</code> with a start and end-state, and
062 * the set adjustables.
063 *
064 * @param sourceState
065 * the beginning state of any path
066 * @param goalState
067 * the end state of any path
068 * @param adjustables
069 * the adjustables of the current requester
070 * @param heuristic
071 * the heuristic of the graph
072 * @param requester
073 * the id of the plan requester
074 */
075 public AStarGraph(State sourceState, State goalState,
076 Collection<Adjustable> adjustables, Heuristic heuristic,
077 SuperLinkID requester) {
078 this.heuristic = heuristic;
079 AStarVertex proxySource = new AStarVertex(sourceState, heuristic
080 .h(sourceState));
081 AStarVertex proxyGoal = new AStarVertex(goalState, 0);
082 sourceVertex = proxySource.toSourceVertex(new Step(adjustables));
083 goalVertex = proxyGoal.toGoalVertex();
084 vertices = new ArrayList<Vertex>();
085 vertices.add(goalVertex);
086 vertices.add(sourceVertex);
087 this.requesterId = requester;
088 ruleEngine = Repository.getRuleEngine();
089 if (logger.isDebugEnabled()) {
090 logger.debug("AStarGraph(State sourceState=" + sourceState
091 + ", State goalState=" + goalState
092 + ", Collection<Adjustable> adjustables=" + adjustables
093 + ", Heuristic heuristic=" + heuristic
094 + ", SuperLinkID id=" + requester + ")");
095 }
096 }
097
098 /**
099 * 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 }
|