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
|
(* virt-builder
* Copyright (C) 2012-2019 Red Hat Inc.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*)
(** The Planner can plan how to reach a goal by carrying out a series
of operations. You tag the input state and the output state, and
give it a list of permitted transitions, and it will return a
multi-step plan (list of transitions) from the input state to the
output state.
For an explanation of the Planner, see:
http://rwmj.wordpress.com/2013/12/14/writing-a-planner-to-solve-a-tricky-programming-optimization-problem/
Tags are described as OCaml association lists. See the OCaml
{!List} module.
Transitions are defined by a function (that the caller supplies)
which returns the possible transitions for a given set of tags,
and for each possible transition, the weight (higher number =
higher cost), and the tag state after that transition.
The returned plan is a list of transitions.
The implementation is a simple breadth-first search of the tree of
states (each edge in the tree is a transition). It doesn't work
very hard to optimize the weights, so the returned plan is
possible, but might not be optimal. *)
type ('name, 'value) tag = 'name * 'value
(** A single tag. *)
type ('name, 'value) tags = ('name, 'value) tag list
(** An assoc-list of tags. *)
type ('name, 'value, 'task) transition =
('name, 'value) tags * 'task * ('name, 'value) tags
(** A transition is the 3 element tuple:
(input tags for this transition,
the task to perform,
the output tags after this transition). *)
type ('name, 'value, 'task) plan = ('name, 'value, 'task) transition list
(** A plan (the returned value from the {!plan} function) is a list
of transitions. *)
type ('name, 'value, 'task) transitions_function =
('name, 'value) tags -> ('task * int * ('name, 'value) tags) list
(** This is the type of the transition function. Given a set of
current tags, it returns the list of possible transitions out,
with a weight (higher number = more expensive) for each and the
resulting set of tags after that transition. *)
val plan : ?max_depth:int -> ('name, 'value, 'task) transitions_function ->
('name, 'value) tags ->
must: ('name, 'value) tags -> must_not: ('name, 'value) tags ->
('name, 'value, 'task) plan option
(** Make a plan.
[plan transitions itags goal_must goal_must_not] works out a
plan, which is a list of tasks that have to be carried out in
order to go from the input tags to the goal.
The goal is passed in as a pair of lists: tags that MUST appear
and tags that MUST NOT appear.
The returned value is a {!plan}.
Returns [None] if no plan was found within [max_depth] transitions. *)
|
