/
Planning.kt
167 lines (152 loc) · 5.71 KB
/
Planning.kt
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
package com.softbankrobotics.pddlplanning
import com.softbankrobotics.pddlplanning.utils.*
/**
* A function interface to output logs from a planner.
*/
typealias LogFunction = (String) -> Unit
/**
* Searches for a solution plan for the given PDDL domain and problem.
* @throws PDDLTranslationException when the parsing or analysis of the PDDL failed.
* @throws PDDLPlanningException when the planning failed.
* @return A list of task that solves the planning problem.
*/
typealias PlanSearchFunction = suspend (String, String, LogFunction?) -> Tasks
/**
* Exception occurring while analyzing a PDDL problem.
*/
class PDDLTranslationException(message: String): RuntimeException(message)
/**
* Exception occurring as a result of finding a plan to a PDDL problem.
*/
class PDDLPlanningException(message: String): RuntimeException(message)
suspend fun adaptProblemAndSearchPlan(
domain: String,
problemBase: String,
objects: Iterable<Instance>,
init: Iterable<Fact>,
log: LogFunction? = null,
searchPlan: PlanSearchFunction
): Tasks {
if (log != null) log("Current objects:\n${objects.joinToString("\n")}")
var problem = replaceObjects(problemBase, objects)
if (log != null) log("Initial state:\n${init.joinToString("\n")}")
problem = replaceInit(problem, init)
val startTime = System.currentTimeMillis()
val plan = searchPlan(domain, problem, log)
val planTime = System.currentTimeMillis() - startTime
if (log != null) log("Found plan in ${planTime}ms:\n${plan.joinToString(")\n(", "(", ")")}")
return plan
}
suspend fun adaptProblemAndSearchPlan(
domain: String,
problemBase: String,
objects: Iterable<Instance>,
init: Iterable<Fact>,
goals: Goals,
log: LogFunction? = null,
searchPlan: PlanSearchFunction
): Tasks {
if (log != null) log("Goals:\n${goals.joinToString("\n")}")
val problem = replaceGoal(problemBase, goals)
return adaptProblemAndSearchPlan(domain, problem, objects, init, log, searchPlan)
}
/**
* Search plan using PDDL Ontology.
*/
suspend fun searchPlan(
types: Collection<Type>,
constants: Collection<Instance>,
predicates: Collection<Expression>,
actions: Collection<Action>,
objects: Collection<Instance>,
init: Collection<Fact>,
goals: Collection<Goal>,
planSearchFunction: PlanSearchFunction
): Tasks {
val domain = createDomain(types, constants, predicates, actions)
// Sometimes constants may be repeated in the :init section.
// Certain planners do not like this, so let us avoid that.
val problem = createProblem(objects - constants, init, goals)
return planSearchFunction(domain, problem, null)
}
/**
* Check problems in PDDL before searching plan using PDDL Ontology.
*/
suspend fun checkProblemAndSearchPlan(
types: Collection<Type>,
constants: Collection<Instance>,
predicates: Collection<Expression>,
actions: Collection<Action>,
objects: Collection<Instance>,
init: Collection<Fact>,
goals: Collection<Goal>,
planSearchFunction: PlanSearchFunction,
log: LogFunction? = null
): Tasks {
if (log != null)
analyzeUnsatisfiedGoals(objects, init, goals, log)
checkErrors(types, constants, predicates, actions, objects, init, goals)
return searchPlan(
types,
constants,
predicates,
actions,
objects,
init,
goals,
planSearchFunction
)
}
fun analyzeUnsatisfiedGoals(
objects: Collection<Instance>,
init: Collection<Fact>,
goals: Collection<Goal>,
log: LogFunction
) {
log("Goal analysis for state:\n${init.joinToString("\n")}")
val evaluatedGoals = goals.map { it to evaluateExpression(it, objects, init) }
log("Evaluated goals:\n${evaluatedGoals.joinToString("\n") {
"${if (it.second) 10003.toChar() else 10060.toChar()} ${it.first}"
}}")
}
fun checkErrors(
types: Collection<Type>,
constants: Collection<Instance>,
predicates: Collection<Expression>,
actions: Collection<Action>,
objects: Collection<Instance>,
init: Collection<Fact>,
goals: Collection<Goal>
) {
// Check that no unknown predicate is used...
fun checkMissing(actual: Set<String>, expected: Set<String>, context: String) {
val missing = actual - expected
if (missing.isNotEmpty())
throw IllegalArgumentException("$context use undefined predicates $missing")
}
val expectedPredicateNames = predicates.map { it.word }.toSet()
// ... in actions...
val involvedPredicateNamesInActions =
actions.flatMap { extractPredicates(it.precondition)
.plus(extractPredicates(it.effect)) }
.toSet()
checkMissing(involvedPredicateNamesInActions, expectedPredicateNames, "actions")
// ... and in goals.
val involvedPredicateNamesInGoals = goals.flatMap { extractPredicates(it) }.toSet()
checkMissing(involvedPredicateNamesInGoals, expectedPredicateNames, "goals")
// Check whether goals mention predicates that are not mentioned in the effects of actions.
val goalPredicates =
goals.flatMap { extractConsequentPredicatesFromExpression(it) }.distinct()
val actionPredicates =
actions.flatMap { extractConsequentPredicatesFromExpression(it.effect) }.distinct()
val unmanagedPredicates = goalPredicates.filter { goal ->
actionPredicates.none { action ->
goal.values.any { it in action.values }
}
}
if (unmanagedPredicates.isNotEmpty())
throw RuntimeException("no action produces effect involving predicates required in goals $unmanagedPredicates")
// TODO: check that instances are not unmanaged
// TODO: check that all predicates are declared
// TODO: check for explicitly contradictory goals
}