| 1 | package dk.deepthought.sidious.planner; |
| 2 | |
| 3 | import org.apache.commons.logging.Log; |
| 4 | import org.apache.commons.logging.LogFactory; |
| 5 | |
| 6 | import dk.deepthought.sidious.greenhouse.ClimaticState; |
| 7 | import dk.deepthought.sidious.greenhouse.SensorInput; |
| 8 | import dk.deepthought.sidious.supportsystem.State; |
| 9 | import dk.deepthought.sidious.supportsystem.SuperLinkID; |
| 10 | |
| 11 | /** |
| 12 | * The class encapsulates the heuristic function of the A*-algorithm. |
| 13 | * <p> |
| 14 | * The heuristic is calculated by evaluating all rules associated with the |
| 15 | * requester of the plan. In this way the estimated cost of getting to the goal |
| 16 | * is very close to the actual distance. |
| 17 | * |
| 18 | * @author Deepthought |
| 19 | * |
| 20 | */ |
| 21 | public final class GreenhouseHeuristic implements Heuristic { |
| 22 | /** |
| 23 | * Logger for this class |
| 24 | */ |
| 25 | private static final Log logger = LogFactory |
| 26 | .getLog(GreenhouseHeuristic.class); |
| 27 | |
| 28 | /** |
| 29 | * The id of the requester. |
| 30 | */ |
| 31 | private final SuperLinkID id; |
| 32 | |
| 33 | /** |
| 34 | * The goal of the search. |
| 35 | */ |
| 36 | private ClimaticState goal; |
| 37 | |
| 38 | /** |
| 39 | * The source of the search. |
| 40 | */ |
| 41 | private ClimaticState source; |
| 42 | |
| 43 | /** |
| 44 | * The base euclidian distance. <code>distance(source, goal)</code>. |
| 45 | */ |
| 46 | private double baseEuclidianDistance = Double.NaN; |
| 47 | |
| 48 | /** |
| 49 | * Constructs a new <code>GreenhouseHeuristic</code> with the specified |
| 50 | * <code>id</code>. |
| 51 | * |
| 52 | * @param id |
| 53 | * the id to the requester. |
| 54 | * @param source |
| 55 | * the source state of any path in the graph |
| 56 | * @param goal |
| 57 | * the goal state of any path in the graph |
| 58 | */ |
| 59 | public GreenhouseHeuristic(final SuperLinkID id, State source, State goal) { |
| 60 | if (id == null || source == null || goal == null) { |
| 61 | logger.error("GreenhouseHeuristic(SuperLinkID id=" + id |
| 62 | + ", State source=" + source + ", State goal=" + goal |
| 63 | + ") - not valid input"); |
| 64 | throw new IllegalArgumentException("null not valid input"); |
| 65 | } |
| 66 | this.id = id; |
| 67 | if (source instanceof ClimaticState) { |
| 68 | this.source = (ClimaticState) source; |
| 69 | } |
| 70 | if (goal instanceof ClimaticState) { |
| 71 | this.goal = (ClimaticState) goal; |
| 72 | } |
| 73 | } |
| 74 | |
| 75 | /** |
| 76 | * This heuristic is based upon a normalized Euclidian distance. |
| 77 | * <p> |
| 78 | * This distance is the distance from the current vertex to the goal divided |
| 79 | * by the distance from source to goal. |
| 80 | * |
| 81 | * @see dk.deepthought.sidious.planner.Heuristic#h(dk.deepthought.sidious.supportsystem.State) |
| 82 | */ |
| 83 | public double h(final State state) { |
| 84 | if (logger.isDebugEnabled()) { |
| 85 | logger.debug("heuristic(State state=" + state + ") - start"); |
| 86 | } |
| 87 | if (state == null) { |
| 88 | String fail = "h(State state=null) - not valid state"; |
| 89 | logger.error(fail); |
| 90 | throw new IllegalArgumentException(fail); |
| 91 | } |
| 92 | double returndouble = 0; |
| 93 | if (state instanceof ClimaticState) { |
| 94 | ClimaticState clima = (ClimaticState) state; |
| 95 | |
| 96 | double normalizedEuclidian = normalizedEuclidian(clima); |
| 97 | returndouble = normalizedEuclidian; |
| 98 | } |
| 99 | if (logger.isDebugEnabled()) { |
| 100 | logger.debug("heuristic(State state=" + state |
| 101 | + ") - end - return value=" + returndouble); |
| 102 | } |
| 103 | return returndouble; |
| 104 | } |
| 105 | |
| 106 | /** |
| 107 | * Calculates the normalized euclidian cost of getting form any state to the |
| 108 | * goal state. |
| 109 | * |
| 110 | * <pre> |
| 111 | * distance(any, goal) / distance(source, goal) |
| 112 | * </pre> |
| 113 | * |
| 114 | * @param state |
| 115 | * the state to calculate the distance from |
| 116 | * |
| 117 | * @return the normalized euclidian cost |
| 118 | */ |
| 119 | private double normalizedEuclidian(ClimaticState state) { |
| 120 | if (Double.isNaN(baseEuclidianDistance)) { |
| 121 | baseEuclidianDistance = euclidianDistanceToGoal(source); |
| 122 | } |
| 123 | double normalizedDistance = euclidianDistanceToGoal(state) |
| 124 | / baseEuclidianDistance; |
| 125 | return normalizedDistance; |
| 126 | } |
| 127 | |
| 128 | /** |
| 129 | * Calculates the euclidian distance to the goal state. |
| 130 | * |
| 131 | * @param state |
| 132 | * the source state |
| 133 | * @return the euclidian distance |
| 134 | */ |
| 135 | double euclidianDistanceToGoal(ClimaticState state) { |
| 136 | if (state.partiallyEquals(goal)) { |
| 137 | return 0; |
| 138 | } |
| 139 | double total = 0; |
| 140 | for (SensorInput sensorFromGoal : goal.getSensors()) { |
| 141 | double sensorValue = sensorFromGoal.getValue(); |
| 142 | for (SensorInput sensorFromState : state.getSensors()) { |
| 143 | if (sensorFromGoal.equalsOnSuperLinkID(sensorFromState)) { |
| 144 | sensorValue -= sensorFromState.getValue(); |
| 145 | total += (sensorValue * sensorValue); |
| 146 | } |
| 147 | } |
| 148 | |
| 149 | } |
| 150 | return Math.sqrt(total); |
| 151 | } |
| 152 | |
| 153 | } |