some examples from a recent conference
(application track at ICAPS 2016):
marine float controlling
tourist group tour organization
electric power generation
ambulance base station placement
electric power acquisition from consumers
satellite controling
reconfigurable manifacturing systems
search-and-tracking
real-world problems
technically complex solutions
For example, the floats can only go up and down but can be moved by the ocean
currents. A probabilistic model tells how the currents change depending on the
depth, so they can be used to move the floats back to their target positions.
At the same time, the floats have to collect data at various depths, where the
currents may move them away.
float = galleggiante
techniques
general methods (propositional satisfiability, integer programming,
…)
planners (e.g., fast-downward)
ad-hoc algorithms
this course: planners and
propositional satisfiability
(but not integer programming, etc.)
very basic example
escaping a maze
state:
current position
goal:
get out of the maze
actions:
allowed moves
so simple?
almost never
(see examples from ICAPS 2016)
what makes it simple?
state = position in the maze
the set of possible states is small
the whole set can be stored in memory and analyzed
but:
simple domain = simple explanation of issues and algorithms
Some issues that may arise in planning also concern cases simple like this, and
some algorithms apply to them. While such simple cases are not of much interest
in practice, they are commonly used for teaching purposes, since explanations
are simpler on simple examples than on complex ones.
more realistic example
deliver parcels
n trucks,
m parcels,
i warehouses,
j routes
every truck can be in a warewouse or on a route
total possibilities: n×(i+j)
every parcel can be in warehouse or on a truck
total possibilities:
mx(n+i)
number of states = n×(i+j)×mx(n+i)
too many to explicitely represent the set of all states
The formulation of the problem is large in spite of being simplified by
disregarding the truck capacity and speed, the length of the routes, etc.