Code trace of EightPuzzleDemo running eightPuzzleGreedyBestFirstDemo notes: ... = aima.core -- class init at load time -- class constructor at instantiation time -- VM Started -- ====== main ====== ====== Construct possible Actions and initial EightPuzzleBoard layouts | -- aima.gui.demo.search.EightPuzzleDemo || -- ...environment.eightpuzzle.EightPuzzleBoard ||| -- ...agent.impl.DynamicAction |||| -- ...agent.impl.ObjectWithDynamicAttributes |||| setAttribute -- ...agent.impl.ObjectWithDynamicAttributes ||| -- ...agent.impl.DynamicAction |||| -- ...agent.impl.ObjectWithDynamicAttributes |||| setAttribute -- ...agent.impl.ObjectWithDynamicAttributes ||| -- ...agent.impl.DynamicAction |||| -- ...agent.impl.ObjectWithDynamicAttributes |||| setAttribute -- ...agent.impl.ObjectWithDynamicAttributes ||| -- ...agent.impl.DynamicAction |||| -- ...agent.impl.ObjectWithDynamicAttributes |||| setAttribute -- ...agent.impl.ObjectWithDynamicAttributes || -- ...environment.eightpuzzle.EightPuzzleBoard || -- ...environment.eightpuzzle.EightPuzzleBoard || -- ...environment.eightpuzzle.EightPuzzleBoard ====== Start eightPuzzleGreedyBestFirstDemo main program | main -- aima.gui.demo.search.EightPuzzleDemo || eightPuzzleGreedyBestFirstDemo -- aima.gui.demo.search.EightPuzzleDemo ||| -- ...environment.eightpuzzle.EightPuzzleFunctionFactory ====== get Actions Function -- returns Set possible from current Board state ||| getActionsFunction -- ...environment.eightpuzzle.EightPuzzleFunctionFactory |||| -- ...environment.eightpuzzle.EightPuzzleFunctionFactory$EPActionsFunction ||||| -- ...environment.eightpuzzle.EightPuzzleFunctionFactory$EPActionsFunction ====== get Result Function -- returns new EightPuzzleBoard after exec of given Action ||| getResultFunction -- ...environment.eightpuzzle.EightPuzzleFunctionFactory |||| -- ...environment.eightpuzzle.EightPuzzleFunctionFactory$EPResultFunction ||||| -- ...environment.eightpuzzle.EightPuzzleFunctionFactory$EPResultFunction ====== get GoalTest Function -- returns true if given Board state matches the Goal state ||| -- ...environment.eightpuzzle.EightPuzzleGoalTest |||| -- ...environment.eightpuzzle.EightPuzzleBoard (Goal state board) ====== instantiate Problem container object ====== using default Step Cost == 1 for each step ||| -- ...search.framework.Problem |||| -- ...search.framework.DefaultStepCostFunction |||| -- ...search.framework.Problem ====== instantiate GraphSearch object ====== implements search() state node descent ||| -- ...search.framework.GraphSearch |||| -- ...search.framework.QueueSearch ||||| -- ...search.framework.NodeExpander |||||| -- ...search.framework.Metrics ====== get search heuristic Function -- returns number of tiles out of place ====== note: this hard codes Goal state defined in EightPuzzleGoalTest ====== the ManhattanHeuristicFunction also hard codes the Goal... ||| -- ...environment.eightpuzzle.MisplacedTilleHeuristicFunction ====== instantiate GreedyBestFirstSearch object ||| -- ...search.informed.GreedyBestFirstSearch |||| -- ...search.informed.GreedyBestFirstEvaluationFunction |||| -- ...search.informed.BestFirstSearch ||||| -- ...search.framework.PrioritySearch ====== instantiate SearchAgent object ====== This runs the SEARCH in the construtor!!! ||| -- ...search.framework.SearchAgent |||| -- ...agent.impl.AbstractAgent ====== GreedyBestFirstSearch.search() -> PrioritySearch.search() |||| search -- ...search.framework.PrioritySearch ====== creates frontier Priority Queue which uses results of ====== getComparator() -> returns GreedyBestFirstEvaluationFunction ||||| getComparator -- ...search.informed.BestFirstSearch |||||| -- ...search.informed.BestFirstSearch$1 ====== KLUDGE: pokes into GraphSearch to set replaceFrontierNodeAtStateCostFunction |||||| setReplaceFrontierNodeAtStateCostFunction -- ...search.framework.GraphSearch ====== PrioritySearch.search() creates N sized frontier Priority Queue for GraphSearch using given comparator function) ||||| -- ...util.datastructure.PriorityQueue ====== Start Searching.... ====== GraphSearch.search() called from PrioritySearch.search() ||||| search -- ...search.framework.GraphSearch ====== GraphSearch.search() clears it's explored and frontier Lists, then calls QueueSearch.search() to do work ====== then calls QueueSearch.search() to do work |||||| search -- ...search.framework.QueueSearch ====== QueueSearch.search() -- Real Search ====== clear Metrics ||||||| clearInstrumentation -- ...search.framework.QueueSearch |||||||| clearInstrumentation -- ...search.framework.NodeExpander ||||||||| set -- ...search.framework.Metrics ====== Get starting state as root Node ||||||| getInitialState -- ...search.framework.Problem ||||||| -- ...search.framework.Node ====== (Don't) Check that we are done already ||||||| isCheckGoalBeforeAddingToFrontier -- ...search.framework.QueueSearch ====== Put root Node into frontier queue ||||||| insert -- ...util.datastructure.PriorityQueue ====== Set size of Metrics to frontier queue size -- dunno why? ||||||| setQueueSize -- ...search.framework.QueueSearch |||||||| set -- ...search.framework.Metrics ====== START SEARCH (finally: loop in QueueSearch.search()) ====== WHILE there are frontier Nodes (and thread still running) ||||||| isEmpty -- ...util.datastructure.PriorityQueue ||||||| currIsCanceled -- ...util.CancelableThread ====== get highest priority frontier Node from QueueSearch.frontier queue ====== and remove it from GraphSearch.frontierState Map ||||||| popNodeFromFrontier -- ...search.framework.GraphSearch |||||||| popNodeFromFrontier -- ...search.framework.QueueSearch ...................... removed a bunch of housekeeping calls ............. ====== Set size of Metrics to frontier queue size -- why each time? ||||||| setQueueSize -- ...search.framework.QueueSearch ====== Now check if we are done ||||||| isCheckGoalBeforeAddingToFrontier -- ...search.framework.QueueSearch ||||||| isGoalState -- ...search.framework.SearchUtils |||||||| getGoalTest -- ...search.framework.Problem |||||||| getState -- ...search.framework.Node |||||||| isGoalState -- ...environment.eightpuzzle.EightPuzzleGoalTest ||||||||| equals -- ...environment.eightpuzzle.EightPuzzleBoard |||||||||| getPositionOf -- ...environment.eightpuzzle.EightPuzzleBoard |||||||||| getPositionOf -- ...environment.eightpuzzle.EightPuzzleBoard ====== Not done... ====== BEGIN Expand the current node to a new frontier set ====== The smarts about what paths to take are coded in this method ||||||| getResultingNodesToAddToFrontier -- ...search.framework.GraphSearch ====== first save old expanding Node state in "explored" Set |||||||| getState -- ...search.framework.Node ================== FOR expandNode ====== make a list of possible Nodes |||||||| expandNode -- ...search.framework.NodeExpander ====== get the various functions we need ||||||||| getActionsFunction -- ...search.framework.Problem ||||||||| getResultFunction -- ...search.framework.Problem ||||||||| getStepCostFunction -- ...search.framework.Problem ====== get a list of Actions we can perform from this Node's state ====== using Actions Function from "Problem" ||||||||| getState -- ...search.framework.Node ||||||||| actions -- ...environment.eightpuzzle.EightPuzzleFunctionFactory$EPActionsFunction ======================== expandNode() FOR each Action in list ====== get a result state for Action execution ====== using Results Function from "Problem" ||||||||| getState -- ...search.framework.Node ||||||||| result -- ...environment.eightpuzzle.EightPuzzleFunctionFactory$EPResultFunction ====== get the cost of the Action execution ====== using Step Cost Function from "Problem" ====== note: this is NOT the heuristic, just the default step cost ||||||||| getState -- ...search.framework.Node ||||||||| c -- ...search.framework.DefaultStepCostFunction ====== add a new Node to childNodes list to return ||||||||| -- ...search.framework.Node |||||||||| -- ...search.framework.Node ================== end FOR loop expandNode ====== set Metrics ||||||||| set -- ...search.framework.Metrics ====== return new Node list ====== GraphSearch.getResultingNodesToAddToFrontier() ====== FOR each Node from expandNode list ====== if it's not in explored or frontier lists, ====== put in addToFrontier list ====== if it's in frontier with higher cost, ====== replace in list ====== return addToFrontier list to QueueSearch.search() ================= END of expand parent Node ================ ====== QueueSearch.search() FOR getResultingNodesToAddToFrontier() ====== Insert addToFrontier Nodes into frontier queue ====== do not check for Goal before adding ||||||| isCheckGoalBeforeAddingToFrontier -- ...search.framework.QueueSearch ================ START insert into queue =================== ||||||| insert -- ...util.datastructure.PriorityQueue ====== use GreedyBestFirstEvaluationFunction with ====== MisplacedTilleHeuristicFunction to order queue |||||||| compare -- ...search.informed.BestFirstSearch$1 ||||||||| compare -- ...search.informed.BestFirstSearch$1 |||||||||| access$0 -- ...search.informed.BestFirstSearch |||||||||| f -- ...search.informed.GreedyBestFirstEvaluationFunction ||||||||||| getState -- ...search.framework.Node ||||||||||| h -- ...environment.eightpuzzle.MisplacedTilleHeuristicFunction |||||||||||| getNumberOfMisplacedTiles -- ...environment.eightpuzzle.MisplacedTilleHeuristicFunction ................... lots of housekeeping ...................... ================= END queue insert ========================= ====== set Metrics Queue size to frontier size -- dunno why... ||||||| setQueueSize -- ...search.framework.QueueSearch ================== back to top of QueueSearch.search() WHILE frontier Node loop ================ ||||||| isEmpty -- ...util.datastructure.PriorityQueue ||||||| currIsCanceled -- ...util.CancelableThread ====== get the next highest priority Node ||||||| popNodeFromFrontier -- ...search.framework.GraphSearch |||||||| popNodeFromFrontier -- ...search.framework.QueueSearch ||||||| setQueueSize -- ...search.framework.QueueSearch ||||||| isCheckGoalBeforeAddingToFrontier -- ...search.framework.QueueSearch ||||||| isGoalState -- ...search.framework.SearchUtils ====== NOT Goal state ... continue expanding ================== FOR loop add to add new frontier nodes ||||||| getResultingNodesToAddToFrontier -- ...search.framework.GraphSearch |||||||| expandNode -- ...search.framework.NodeExpander ||||||| isCheckGoalBeforeAddingToFrontier -- ...search.framework.QueueSearch ||||||| insert -- ...util.datastructure.PriorityQueue ||||||| setQueueSize -- ...search.framework.QueueSearch ================== END WHILE loop on frontier Nodes ============ ================== N times until Goal is met ============ ................................ ====== If we should check for Goal now -- yes -- then do it ||||||| isCheckGoalBeforeAddingToFrontier -- ...search.framework.QueueSearch ||||||| isGoalState -- ...search.framework.SearchUtils |||||||| getGoalTest -- ...search.framework.Problem |||||||| getState -- ...search.framework.Node |||||||| isGoalState -- ...environment.eightpuzzle.EightPuzzleGoalTest ........................whole bunch of housekeeping ..................... ====== This IS the GOAL -- return out of QueueSearch.search() ====== get and save the total path cost ||||||| getPathCost -- ...search.framework.Node ||||||| setPathCost -- ...search.framework.QueueSearch |||||||| set -- ...search.framework.Metrics ||||||| getPathFromRoot -- ...search.framework.Node |||||||| isRootNode -- ...search.framework.Node |||||||| getParent -- ...search.framework.Node |||||||| isRootNode -- ...search.framework.Node |||||||| getParent -- ...search.framework.Node |||||||| isRootNode -- ...search.framework.Node |||||||| getParent -- ...search.framework.Node |||||||| isRootNode -- ...search.framework.Node ======= Get and return the Actions to perform in solution ||||||| actionsFromNodes -- ...search.framework.SearchUtils |||||||| getAction -- ...search.framework.Node |||||||| getAction -- ...search.framework.Node |||||||| getAction -- ...search.framework.Node ====== Print out results |||| getMetrics -- ...search.framework.PrioritySearch ||||| getMetrics -- ...search.framework.NodeExpander ||| getActions -- ...search.framework.SearchAgent ||| printActions -- aima.gui.demo.search.EightPuzzleDemo ||| getInstrumentation -- ...search.framework.SearchAgent ||| printInstrumentation -- aima.gui.demo.search.EightPuzzleDemo ====== main end ====== -- The application exited --