This chapter casts the problem of an agent deciding how to solve a goal as the problem of searching to find a path in a graph.
You can run each cell by selecting it and pressing Ctrl+Enter in Windows or Shift+Return in MacOS. Alternatively, you can click the Play button in the toolbar, to the left of the stop button. For more information, check out our AISpace2 Tutorial.
Feel free to modify our codes either in this notebook or somewhere outside (e.g. python files in /aipython/). If you want to modify our codes outside, you might find this helpful for how your changes can take effect.
You need to run the following command to import our pre-defined problems.
In [ ]:
# Run this to import pre-defined problems
from aipython.searchProblem import search_simple1, search_simple2, search_edgeless, search_cyclic_delivery, search_acyclic_delivery, search_tree, search_extended_tree, search_cyclic, search_vancouver_neighbour, search_misleading_heuristic, search_multiple_path_pruning, search_module_4_graph, search_module_5_graph, search_bicycle_courier_acyclic, search_bicycle_courier_cyclic
You can also define your own problems (how?).
You need to run the following command to import utilities that support your self-defined problems.
In [ ]:
# Run this to import utilities that support self-defined problems
from aipython.searchProblem import Arc, Search_problem_from_explicit_graph
In depth-first search, the frontier acts like a LIFO (last-in, first-out) stack of paths. This means that the path selected and removed from the frontier at any time is the last path that was added. Depth-first search is appropriate when space is restricted, or when there are many solutions. On the other hand, depth-first search is not appropriate if it is possible to get stuck into infinite paths or if solutions exist at shallow depths.
In [ ]:
from aipython.searchGeneric import Searcher
s = Searcher(problem=search_simple2)
# Visualization options
# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options
s.sleep_time = 0.2 # The time, in seconds, between each step in auto solving
s.line_width = 2.0 # The thickness of edges
s.text_size = 13 # The fontsize of the text
s.detail_level = 2 # 0=no text, 1=truncated text, 2=full text
s.show_edge_costs = True
s.show_node_heuristics = False
# Controls the layout engine used. Either "force" for force layout, or "tree".
s.layout_method = "force"
# s.layout_method = "tree"
# Display the widget
display(s)
s.search()
A* search uses both path cost and heuristic information in its selection of which path to expand. For each path on the frontier, A* uses an estimate of the total path cost from the start node to a goal node constrained to follow that path initially. The estimated total path cost is the sum of the cost of the path found $\text{cost}(p)$ and the heuristic function $h(p)$, which estimates the cost from the end of $p$ to the goal.
In [ ]:
from aipython.searchGeneric import AStarSearcher
s_astar = AStarSearcher(problem=search_simple1)
# Visualization options
# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options
s_astar.sleep_time = 0.2 # The time, in seconds, between each step in auto solving
s_astar.line_width = 2.0 # The thickness of edges
s_astar.text_size = 13 # The fontsize of the text
s_astar.detail_level = 2 # 0=no text, 1=truncated text, 2=full text
s_astar.show_edge_costs = True
s_astar.show_node_heuristics = True
# Display the widget
display(s_astar)
s_astar.search()
There is often more than one path to a node. If only one path is required, a search algorithm can prune from the frontier any path that leads to a node to which it has already found a path. Multiple-path pruning is implemented by maintaining an explored set (traditionally called closed list) of nodes that are at the end of paths that have been expanded. The explored set is initially empty. When a path $⟨n_0,…,n_k⟩$ is selected , if $n_k$ is already in the explored set, the path can be discarded. Otherwise, $n_k$ is added to the explored set, and the algorithm proceeds as before.
In [ ]:
from aipython.searchMPP import SearcherMPP
s_mpp = SearcherMPP(problem=search_simple1)
# Visualization options
# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options
s_mpp.sleep_time = 0.2 # The time, in seconds, between each step in auto solving
s_mpp.line_width = 2.0 # The thickness of edges
s_mpp.text_size = 13 # The fontsize of the text
s_mpp.detail_level = 1 # 0=no text, 1=truncated text, 2=full text
s_mpp.show_edge_costs = True
s_mpp.show_node_heuristics = True
# Display the widget
display(s_mpp)
s_mpp.search()
Depth-first branch-and-bound search is a way to combine the space saving of depth-first search with heuristic information for finding optimal paths. It is particularly applicable when there are many paths to a goal. As in A* search, the heuristic function h$(n)$ is non-negative and less than or equal to the cost of a lowest-cost path from n to a goal node.
The idea of a branch-and-bound search is to maintain the lowest cost $b$ ("bound") of a path to a goal found so far. If the search encounters a path $p$ such that $\text{cost}(p)+h(p)≥b$, path $p$ can be pruned. If a non-pruned path to a goal is found, it must be better than the previous best path. This new solution is remembered and bound is set to the cost of this new solution. The searcher then proceeds to search for a better solution.
In [ ]:
from aipython.searchBranchAndBound import DF_branch_and_bound
s_dfbb = DF_branch_and_bound(problem=search_simple1)
# Visualization options
# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options
s_dfbb.sleep_time = 0.2 # The time, in seconds, between each step in auto solving
s_dfbb.line_width = 2.0 # The thickness of edges
s_dfbb.text_size = 13 # The fontsize of the text
s_dfbb.detail_level = 2 # 0=no text, 1=truncated text, 2=full text
s_dfbb.show_edge_costs = True
s_dfbb.show_node_heuristics = True
# Display the widget
display(s_dfbb)
s_dfbb.search()
In [ ]: