content: package aima.core.environment.wumpusworld;
  
  import aima.core.agent.Notifier;
  import aima.core.agent.impl.SimpleAgent;
  import aima.core.logic.propositional.inference.DPLL;
  import aima.core.logic.propositional.inference.EntailmentChecker;
  import aima.core.search.framework.Metrics;
  import aima.core.search.framework.SearchForActions;
  import aima.core.search.framework.problem.GeneralProblem;
  import aima.core.search.framework.problem.Problem;
  import aima.core.search.framework.qsearch.GraphSearch;
  import aima.core.search.informed.AStarSearch;
  import aima.core.util.SetOps;
  
  import java.util.*;
  
  /**
   * Artificial Intelligence A Modern Approach (3rd Edition): page 270.<br>
   * <br>
   * 
   * <pre>
   * <code>
   * function HYBRID-WUMPUS-AGENT(percept) returns an action
   *   inputs: percept, a list, [stench, breeze, glitter, bump, scream]
   *   persistent: KB, a knowledge base, initially the temporal "wumpus physics"
   *               t, a counter, initially 0, indicating time
   *               plan, an action sequence, initially empty
   * 
   *   TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))
   *   TELL the KB the temporal "physics" sentences for time t
   *   safe <- {[x, y] : ASK(KB, OK<sup>t</sup><sub>x,y</sub>) = true}
   *   if ASK(KB, Glitter<sup>t</sup>) = true then
   *      plan <- [Grab] + PLAN-ROUTE(current, {[1,1]}, safe) + [Climb]
   *   if plan is empty then
   *      unvisited <- {[x, y] : ASK(KB, L<sup>t'</sup><sub>x,y</sub>) = false for all t' &le; t}
   *      plan <- PLAN-ROUTE(current, unvisited &cap; safe, safe)
   *   if plan is empty and ASK(KB, HaveArrow<sup>t</sup>) = true then
   *      possible_wumpus <- {[x, y] : ASK(KB, ~W<sub>x,y</sub>) = false}
   *      plan <- PLAN-SHOT(current, possible_wumpus, safe)
   *   if plan is empty then //no choice but to take a risk
   *      not_unsafe <- {[x, y] : ASK(KB, ~OK<sup>t</sup><sub>x,y</sub>) = false}
   *      plan <- PLAN-ROUTE(current, unvisited &cap; not_unsafe, safe)
   *   if plan is empty then
   *      plan <- PLAN-ROUTE(current, {[1,1]}, safe) + [Climb]
   *   action <- POP(plan)
   *   TELL(KB, MAKE-ACTION-SENTENCE(action, t))
   *   t <- t+1
   *   return action
   * 
   * --------------------------------------------------------------------------------
   * 
   * function PLAN-ROUTE(current, goals, allowed) returns an action sequence
   *   inputs: current, the agent's current position
   *           goals, a set of squares; try to plan a route to one of them
   *           allowed, a set of squares that can form part of the route 
   *    
   *   problem <- ROUTE-PROBLEM(current, goals, allowed)
   *   return A*-GRAPH-SEARCH(problem)
   * </code>
   * </pre>
   * 
   * Figure 7.20 A hybrid agent program for the wumpus world. It uses a
   * propositional knowledge base to infer the state of the world, and a
   * combination of problem-solving search and domain-specific code to decide what
   * actions to take
   * 
   * @author Federico Baron
   * @author Alessandro Daniele
   * @author Ciaran O'Reilly
   * @author Ruediger Lunde
   */
  public class HybridWumpusAgent extends SimpleAgent<WumpusPercept, WumpusAction> {
  
  	/// persistent: KB, a knowledge base, initially the atemporal "wumpus physics"
  	private WumpusKnowledgeBase kb;
  	protected AgentPosition start;
  	/** The agent's current position. */
  	protected AgentPosition currentPosition;
  	/// t, a counter, initially 0, indicating time
  	protected int t = 0;
  	/// plan, an action sequence, initially empty
  	protected Queue<WumpusAction> plan = new LinkedList<>(); // FIFOQueue
  	private final Notifier notifier;
  
  	public HybridWumpusAgent() {
  		// i.e. default is a 4x4 world as depicted in figure 7.2
  		this(4, 4, new AgentPosition(1, 1, AgentPosition.Orientation.FACING_NORTH));
  	}
  
  	public HybridWumpusAgent(int caveXDim, int caveYDim, AgentPosition start) {
  		this(caveXDim, caveYDim, start, new DPLL(), null);
  	}
  
  	public HybridWumpusAgent(int caveXDim, int caveYDim, AgentPosition start, EntailmentChecker checker,
  							 Notifier notifier) {
  		this(caveXDim, caveYDim, start, new WumpusKnowledgeBase(caveXDim, caveYDim, start, checker), notifier);
  	}
  
  	public HybridWumpusAgent(int caveXDim, int caveYDim, AgentPosition start, WumpusKnowledgeBase kb,
  							 Notifier notifier) {
  		this.kb = kb;
  		this.start = start;
  		this.currentPosition = start;
  		this.notifier = notifier;
  	}
  
  	public WumpusKnowledgeBase getKB() {
  		return kb;
  	}
  
  	/**
  	 * function HYBRID-WUMPUS-AGENT(percept) returns an action<br>
  	 * 
  	 * @param percept
  	 *            a list, [stench, breeze, glitter, bump, scream]
  	 * 
  	 * @return an action the agent should take.
  	 */
  	@Override
  	public Optional<WumpusAction> act(WumpusPercept percept) {
  
  		/// TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))
  		kb.makePerceptSentence(percept, t);
  		/// TELL the KB the temporal "physics" sentences for time t
  		kb.tellTemporalPhysicsSentences(t);
  
  		Set<Room> safe = null;
  		Set<Room> unvisited = null;
  
  		// Optimization: Do not ask anything during plan execution (different from pseudo-code)
  		if (plan.isEmpty()) {
  			notifyViews("Reasoning (t=" + t + ", Percept=" + percept + ") ...");
  			currentPosition = kb.askCurrentPosition(t);
  			notifyViews("Ask position -> " + currentPosition);
  			/// safe <- {[x, y] : ASK(KB, OK<sup>t</sup><sub>x,y</sub>) = true}
  			safe = kb.askSafeRooms(t);
  			notifyViews("Ask safe -> " + safe);
  		}
  
  		/// if ASK(KB, Glitter<sup>t</sup>) = true then (can only be true when plan is empty!)
  		if (plan.isEmpty() && kb.askGlitter(t)) {
  			/// plan <- [Grab] + PLAN-ROUTE(current, {[1,1]}, safe) + [Climb]
  			Set<Room> goals = new LinkedHashSet<>();
  			goals.add(start.getRoom());
  			plan.add(WumpusAction.GRAB);
  			plan.addAll(planRouteToRooms(goals, safe));
  			plan.add(WumpusAction.CLIMB);
  		}
  
  		/// if plan is empty then
  		if (plan.isEmpty()) {
  			/// unvisited <- {[x, y] : ASK(KB, L<sup>t'</sup><sub>x,y</sub>) = false for all t' &le; t}
  			unvisited = kb.askUnvisitedRooms(t);
  			notifyViews("Ask unvisited -> " + unvisited);
  			/// plan <- PLAN-ROUTE(current, unvisited &cap; safe, safe)
  			plan.addAll(planRouteToRooms(SetOps.intersection(unvisited, safe), safe));
  		}
  
  		/// if plan is empty and ASK(KB, HaveArrow<sup>t</sup>) = true then
  		if (plan.isEmpty() && kb.askHaveArrow(t)) {
  			/// possible_wumpus <- {[x, y] : ASK(KB, ~W<sub>x,y</sub>) = false}
  			Set<Room> possibleWumpus = kb.askPossibleWumpusRooms(t);
  			notifyViews("Ask possible Wumpus positions -> " + possibleWumpus);
  			/// plan <- PLAN-SHOT(current, possible_wumpus, safe)
  			plan.addAll(planShot(possibleWumpus, safe));
  		}
  
  		/// if plan is empty then (no choice but to take a risk)
  		if (plan.isEmpty()) {
  			/// not_unsafe <- {[x, y] : ASK(KB, ~OK<sup>t</sup><sub>x,y</sub>) = false}
  			Set<Room> notUnsafe = kb.askNotUnsafeRooms(t);
  			notifyViews("Ask not unsafe -> " + notUnsafe);
  			/// plan <- PLAN-ROUTE(current, unvisited &cap; not_unsafe, safe)
  			// Correction: Last argument must be not_unsafe!
  			plan.addAll(planRouteToRooms(unvisited, notUnsafe));
  		}
  
  		/// if plan is empty then
  		if (plan.isEmpty()) {
  			notifyViews("Going home.");
  			/// plan PLAN-ROUTE(current, {[1,1]}, safe) + [Climb]
  			Set<Room> goal = new LinkedHashSet<>();
  			goal.add(start.getRoom());
  			plan.addAll(planRouteToRooms(goal, safe));
  			plan.add(WumpusAction.CLIMB);
  		}
  		/// action <- POP(plan)
  		WumpusAction action = plan.remove();
  		/// TELL(KB, MAKE-ACTION-SENTENCE(action, t))
  		kb.makeActionSentence(action, t);
  		/// t <- t+1
  		t = t + 1;
  		/// return action
  		return Optional.of(action);
  	}
  
  	/**
  	 * Returns a sequence of actions using A* Search.
  	 *
  	 * @param goals
  	 *            a set of squares; try to plan a route to one of them
  	 * @param allowed
  	 *            a set of squares that can form part of the route
  	 * 
  	 * @return the best sequence of actions that the agent have to do to reach a
  	 *         goal from the current position.
  	 */
  	public List<WumpusAction> planRouteToRooms(Set<Room> goals, Set<Room> allowed) {
  		final Set<AgentPosition> goalPositions = new LinkedHashSet<>();
  		for (Room goalRoom : goals) {
  			int x = goalRoom.getX();
  			int y = goalRoom.getY();
  			for (AgentPosition.Orientation orientation : AgentPosition.Orientation.values())
  				goalPositions.add(new AgentPosition(x, y, orientation));
  		}
  		return planRoute(goalPositions, allowed);
  	}
  
  	/**
  	 * Returns a sequence of actions using A* Search.
  	 *
  	 * @param goals
  	 *            a set of agent positions; try to plan a route to one of them
  	 * @param allowed
  	 *            a set of squares that can form part of the route
  	 *
  	 * @return the best sequence of actions that the agent have to do to reach a
  	 *         goal from the current position.
  	 */
  	public List<WumpusAction> planRoute(Set<AgentPosition> goals, Set<Room> allowed) {
  
  		WumpusCave cave = new WumpusCave(kb.getCaveXDimension(), kb.getCaveYDimension()).setAllowed(allowed);
  		Problem<AgentPosition, WumpusAction> problem = new GeneralProblem<>(currentPosition,
  				WumpusFunctions.createActionsFunction(cave),
  				WumpusFunctions.createResultFunction(cave), goals::contains);
  		SearchForActions<AgentPosition, WumpusAction> search =
  				new AStarSearch<>(new GraphSearch<>(), WumpusFunctions.createManhattanDistanceFunction(goals));
  		Optional<List<WumpusAction>> actions = search.findActions(problem);
  
  		return actions.orElse(Collections.emptyList());
  	}
  
  	/**
  	 * @param possibleWumpus
  	 *            a set of squares where we don't know that there isn't the
  	 *            wumpus.
  	 * @param allowed
  	 *            a set of squares that can form part of the route
  	 * 
  	 * @return the sequence of actions to reach the nearest square that is in
  	 *         line with a possible wumpus position. The last action is a shot.
  	 */
  	public List<WumpusAction> planShot(Set<Room> possibleWumpus, Set<Room> allowed) {
  
  		Set<AgentPosition> shootingPositions = new LinkedHashSet<>();
  
  		for (Room room : possibleWumpus) {
  			int x = room.getX();
  			int y = room.getY();
  
  			for (int i = 1; i <= kb.getCaveXDimension(); i++) {
  				if (i < x)
  					shootingPositions.add(new AgentPosition(i, y, AgentPosition.Orientation.FACING_EAST));
  				if (i > x)
  					shootingPositions.add(new AgentPosition(i, y, AgentPosition.Orientation.FACING_WEST));
  			}
  			for (int i = 1; i <= kb.getCaveYDimension(); i++) {
  				if (i < y)
  					shootingPositions.add(new AgentPosition(x, i, AgentPosition.Orientation.FACING_NORTH));
  				if (i > y)
  					shootingPositions.add(new AgentPosition(x, i, AgentPosition.Orientation.FACING_SOUTH));
  			}
  		}
  
  		// Can't have a shooting position from any of the rooms the wumpus could reside
  		for (Room room : possibleWumpus)
  			for (AgentPosition.Orientation orientation : AgentPosition.Orientation.values())
  				shootingPositions.remove(new AgentPosition(room.getX(), room.getY(), orientation));
  
  		List<WumpusAction> actions = new ArrayList<>(planRoute(shootingPositions, allowed));
  		actions.add(WumpusAction.SHOOT);
  		return actions;
  	}
  
  	public Metrics getMetrics() {
  		return kb.getMetrics();
  	}
  
  	protected void notifyViews(String msg) {
  		if (notifier != null)
  			notifier.notify(msg);
  	}
  }