-
Notifications
You must be signed in to change notification settings - Fork 810
Expand file tree
/
Copy pathOnlineDFSAgent.java
More file actions
187 lines (169 loc) · 5.95 KB
/
Copy pathOnlineDFSAgent.java
File metadata and controls
187 lines (169 loc) · 5.95 KB
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
package aima.core.search.online;
import java.util.*;
import java.util.function.Function;
import aima.core.agent.Action;
import aima.core.agent.impl.SimpleAgent;
import aima.core.search.framework.problem.OnlineSearchProblem;
import aima.core.util.datastructure.Pair;
import aima.core.util.datastructure.TwoKeyHashMap;
/**
* Artificial Intelligence A Modern Approach (3rd Edition): Figure 4.21, page
* 150.<br>
* <br>
*
* <pre>
* function ONLINE-DFS-AGENT(s') returns an action
* inputs: s', a percept that identifies the current state
* persistent: result, a table, indexed by state and action, initially empty
* untried, a table that lists, for each state, the actions not yet tried
* unbacktracked, a table that lists, for each state, the backtracks not yet tried
* s, a, the previous state and action, initially null
*
* if GOAL-TEST(s') then return stop
* if s' is a new state (not in untried) then untried[s'] <- ACTIONS(s')
* if s is not null then
* result[s, a] <- s'
* add s to the front of the unbacktracked[s']
* if untried[s'] is empty then
* if unbacktracked[s'] is empty then return stop
* else a <- an action b such that result[s', b] = POP(unbacktracked[s'])
* else a <- POP(untried[s'])
* s <- s'
* return a
* </pre>
*
* Figure 4.21 An online search agent that uses depth-first exploration. The
* agent is applicable only in state spaces in which every action can be
* "undone" by some other action.<br>
*
* @param <P> The type used to represent percepts
* @param <S> The type used to represent states
* @param <A> The type of the actions to be used to navigate through the state space
* @author Ciaran O'Reilly
* @author Ruediger Lunde
*
*/
public class OnlineDFSAgent<P, S, A extends Action> extends SimpleAgent<P, A> {
private OnlineSearchProblem<S, A> problem;
private Function<P, S> ptsFn;
/// persistent: result, a table, indexed by state and action, initially empty
private final TwoKeyHashMap<S, A, S> result = new TwoKeyHashMap<>();
/// untried, a table that lists, for each state, the actions not yet tried
private final Map<S, List<A>> untried = new HashMap<>();
/// unbacktracked, a table that lists, for each state, the backtracks not yet tried
private final Map<S, List<S>> unbacktracked = new HashMap<>();
/// s, a, the previous state and action, initially null
private S s = null;
private A a = null;
/**
* Constructs an online DFS agent with the specified search problem and
* percept to state function.
*
* @param problem
* an online search problem for this agent to solve
* @param ptsFn
* a function which returns the problem state associated with a
* given Percept.
*/
public OnlineDFSAgent(OnlineSearchProblem<S, A> problem, Function<P, S> ptsFn) {
setProblem(problem);
setPerceptToStateFunction(ptsFn);
}
/// function ONLINE-DFS-AGENT(s') returns an action
/// inputs: s', a percept that identifies the current state
@Override
public Optional<A> act(P psPrimed) {
S sPrimed = ptsFn.apply(psPrimed);
/// if GOAL-TEST(s') then return stop
if (problem.testGoal(sPrimed)) {
a = null;
} else {
/// if s' is a new state (not in untried) then untried[s'] <- ACTIONS(s')
if (!untried.containsKey(sPrimed))
untried.put(sPrimed, problem.getActions(sPrimed));
/// if s is not null then do
if (s != null) {
// Note: If I've already seen the result of this
// [s, a] then don't put it back on the unbacktracked
// list otherwise you can keep oscillating
// between the same states endlessly.
if (!(sPrimed.equals(result.get(s, a)))) {
/// result[s, a] <- s'
result.put(s, a, sPrimed);
// Ensure the unbacktracked always has a list for s'
if (!unbacktracked.containsKey(sPrimed))
unbacktracked.put(sPrimed, new ArrayList<>());
/// add s to the front of the unbacktracked[s']
unbacktracked.get(sPrimed).add(0, s);
}
}
/// if untried[s'] is empty then
if (untried.get(sPrimed).isEmpty()) {
/// if unbacktracked[s'] is empty then return stop
if (unbacktracked.get(sPrimed).isEmpty()) {
a = null;
} else {
/// else a <- an action b such that result[s', b] = POP(unbacktracked[s'])
S popped = unbacktracked.get(sPrimed).remove(0);
for (Pair<S, A> sa : result.keySet()) {
if (sa.getFirst().equals(sPrimed) && result.get(sa).equals(popped)) {
a = sa.getSecond();
break;
}
}
}
} else {
/// else a <- POP(untried[s'])
a = untried.get(sPrimed).remove(0);
}
}
if (a == null)
// I'm either at the Goal or can't get to it, which in either case I'm finished so just die.
setAlive(false);
/// s <- s'
s = sPrimed;
/// return a
return Optional.ofNullable(a);
}
/**
* Returns the search problem for this agent.
*
* @return the search problem for this agent.
*/
public OnlineSearchProblem<S, A> getProblem() {
return problem;
}
/**
* Sets the search problem for this agent to solve.
*
* @param problem
* the search problem for this agent to solve.
*/
public void setProblem(OnlineSearchProblem<S, A> problem) {
this.problem = problem;
result.clear();
untried.clear();
unbacktracked.clear();
s = null;
a = null;
setAlive(true);
}
/**
* Returns the percept to state function of this agent.
*
* @return the percept to state function of this agent.
*/
public Function<P, S> getPerceptToStateFunction() {
return ptsFn;
}
/**
* Sets the percept to state functinon of this agent.
*
* @param ptsFn
* a function which returns the problem state associated with a
* given Percept.
*/
public void setPerceptToStateFunction(Function<P, S> ptsFn) {
this.ptsFn = ptsFn;
}
}