-
Notifications
You must be signed in to change notification settings - Fork 1
/
run_search.py
137 lines (111 loc) · 5.53 KB
/
run_search.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
import argparse
from timeit import default_timer as timer
from aimacode.search import InstrumentedProblem
from aimacode.search import (breadth_first_search, astar_search,
breadth_first_tree_search, depth_first_graph_search, uniform_cost_search,
greedy_best_first_graph_search, depth_limited_search,
recursive_best_first_search)
from my_air_cargo_problems import air_cargo_p1, air_cargo_p2, air_cargo_p3
PROBLEM_CHOICE_MSG = """
Select from the following list of air cargo problems. You may choose more than
one by entering multiple selections separated by spaces.
"""
SEARCH_METHOD_CHOICE_MSG = """
Select from the following list of search functions. You may choose more than
one by entering multiple selections separated by spaces.
"""
INVALID_ARG_MSG = """
You must either use the -m flag to run in manual mode, or use both the -p and
-s flags to specify a list of problems and search algorithms to run. Valid
choices for each include:
"""
PROBLEMS = [["Air Cargo Problem 1", air_cargo_p1],
["Air Cargo Problem 2", air_cargo_p2],
["Air Cargo Problem 3", air_cargo_p3]]
SEARCHES = [["breadth_first_search", breadth_first_search, ""],
['breadth_first_tree_search', breadth_first_tree_search, ""],
['depth_first_graph_search', depth_first_graph_search, ""],
['depth_limited_search', depth_limited_search, ""],
['uniform_cost_search', uniform_cost_search, ""],
['recursive_best_first_search', recursive_best_first_search, 'h_1'],
['greedy_best_first_graph_search', greedy_best_first_graph_search, 'h_1'],
['astar_search', astar_search, 'h_1'],
['astar_search', astar_search, 'h_ignore_preconditions'],
['astar_search', astar_search, 'h_pg_levelsum'],
]
class PrintableProblem(InstrumentedProblem):
""" InstrumentedProblem keeps track of stats during search, and this
class modifies the print output of those statistics for air cargo
problems.
"""
def __repr__(self):
return '{:^10d} {:^10d} {:^10d}'.format(self.succs, self.goal_tests, self.states)
def run_search(problem, search_function, parameter=None):
start = timer()
ip = PrintableProblem(problem)
if parameter is not None:
node = search_function(ip, parameter)
else:
node = search_function(ip)
end = timer()
print("\nExpansions Goal Tests New Nodes")
print("{}\n".format(ip))
show_solution(node, end - start)
print()
def manual():
print(PROBLEM_CHOICE_MSG)
for idx, (name, _) in enumerate(PROBLEMS):
print(" {!s}. {}".format(idx+1, name))
p_choices = input("> ").split()
print(SEARCH_METHOD_CHOICE_MSG)
for idx, (name, _, heuristic) in enumerate(SEARCHES):
print(" {!s}. {} {}".format(idx+1, name, heuristic))
s_choices = input("> ").split()
main(p_choices, s_choices)
print("\nYou can run this selection again automatically from the command " +
"line\nwith the following command:")
print("\n python {} -p {} -s {}\n".format(__file__,
" ".join(p_choices),
" ".join(s_choices)))
def main(p_choices, s_choices):
problems = [PROBLEMS[i-1] for i in map(int, p_choices)]
searches = [SEARCHES[i-1] for i in map(int, s_choices)]
for pname, p in problems:
for sname, s, h in searches:
hstring = h if not h else " with {}".format(h)
print("\nSolving {} using {}{}...".format(pname, sname, hstring))
_p = p()
_h = None if not h else getattr(_p, h)
run_search(_p, s, _h)
def show_solution(node, elapsed_time):
print("Plan length: {} Time elapsed in seconds: {}".format(len(node.solution()), elapsed_time))
for action in node.solution():
print("{}{}".format(action.name, action.args))
if __name__=="__main__":
parser = argparse.ArgumentParser(description="Solve air cargo planning problems " +
"using a variety of state space search methods including uninformed, greedy, " +
"and informed heuristic search.")
parser.add_argument('-m', '--manual', action="store_true",
help="Interactively select the problems and searches to run.")
parser.add_argument('-p', '--problems', nargs="+", choices=range(1, len(PROBLEMS)+1), type=int, metavar='',
help="Specify the indices of the problems to solve as a list of space separated values. Choose from: {!s}".format(list(range(1, len(PROBLEMS)+1))))
parser.add_argument('-s', '--searches', nargs="+", choices=range(1, len(SEARCHES)+1), type=int, metavar='',
help="Specify the indices of the search algorithms to use as a list of space separated values. Choose from: {!s}".format(list(range(1, len(SEARCHES)+1))))
args = parser.parse_args()
if args.manual:
manual()
elif args.problems and args.searches:
main(list(sorted(set(args.problems))), list(sorted(set((args.searches)))))
else:
print()
parser.print_help()
print(INVALID_ARG_MSG)
print("Problems\n-----------------")
for idx, (name, _) in enumerate(PROBLEMS):
print(" {!s}. {}".format(idx+1, name))
print()
print("Search Algorithms\n-----------------")
for idx, (name, _, heuristic) in enumerate(SEARCHES):
print(" {!s}. {} {}".format(idx+1, name, heuristic))
print()
print("Use manual mode for interactive selection:\n\n\tpython run_search.py -m\n")