The Travelling and Purchase Problem Domain
==========================================
This is a relatively recent planning domain that has been investigating in
Operation Research (OR) for several years. The Travelling Purchase Problem
(TPP) is a known generalization of the Travelling Salesman Problem, and is
defined as follows. We have a set of products and a set of markets. Each
market is provided with a limited amount of each product at a known
price. The TPP consists in selecting a subset of markets such that a given
demand of each product can be purchased, minimizing the routing cost and
the purchasing cost. This problem arises in several applications, mainly
in routing and scheduling contexts, and it is NP-hard. In OR, computing
optimal or near optimal solutions for TPP instances is still an active
research topic.
For IPC-5, we have formalized several variants of this domain in PDDL.
One of them is equivalent to the original TPP, while the others are
different formulations or significant (we believe and hope) extensions.
In all these domain variants, plan quality is important, although
for some instances even finding an arbitrary solution could be quite
difficult for a fully-automated planner. Note that for this domain we
have both a Metric version (no time) and a MetricTemporal version. The
metric version is a PDDL formulation that is equivalent to the original
formulation of TPP in OR.
Domain Variants
===============
We start the description from the Metric version because it is the one
equivalent to the original formulation of TPP.
TPP Metric
----------
This version is equivalent to the original formulation of TPP in OR. There
are only three operators, two of which are used to model the purchasing
actions: "buy-all" and "buy-allneeded". The first buys at a certain market
(?m) the whole amount of a good (?g) sold by the market (?m and ?g are
operator parameters); while the second one buys at ?m the amount of ?g
that is needed to complete the purchase of ?g (as specified in the problem
goals).
Note that every market is *directly* connected to every other market and
to the depots. Moreover, there is only one depot and only one truck.
TPP propositional
-----------------
This version models a variant of the original TPP where: (1) there can be
more than one depot and more than one truck; (2) the amount of goods are
discrete and represented by qualitative levels; (3) every type of good has
the same price, independent from the market where we buy it; (4) there are
two new operators for loading and unloading goods to/from trucks (5) markets
and depots can be indirectly connected.
TPP SimplePreferences
---------------------
The operators in this domain are the same as in the propositional version.
The difference is in the goals. All goals are soft goals (preferences).
These preferences concern maximizing the level of goods that are stored in
the depots, constraints between the levels of different stored goods, and
the safety condition that all purchased goods are stored at some market.
Note that there is an equivalent sub-version, "GroundedPreferences",
where the quantified variables appearing in the preferences have been
instantiated. This is a sub-directory of the directory containing the
SimplePreference version.
TPP Qualitative preferences
---------------------------
The operators in this version are the same as in the propositional version.
All goals are preferences concerning maximizing, for every good, the
purchased and stored levels. This version includes preferences over
trajectory constraints. These are constraints between the levels of two
types of stored goods; constraints about the use of the trucks for loading
goods; constraints imposing the use of every truck. Moreover, we have the
preference that in the final state all purchased goods are stored at some
depot.
TPP MetricTemporal
------------------
With respect to the simpler Metric version, which is equivalent to the
original formulation of TPP, this version has the the following main
differences: same as points (1), (4), (5) illustrated in the description of
the Propositional variants; each action has a duration and the plan quality
is a linear combination of total-time (makespan) and the total cost of
traveling and purchasing; the operator "buyall" has a "rebate" rate (if
you buy the whole amount of a good that is sold at a market, then you
have a discount).
TPP MetricTemporalConstraints
-----------------------------
The operators in this version are the same as in the MetricTemporal
version. In addition, in the domain file, we have some strong constraints
imposing that in the final state all purchased goods are stored, every
market can be visited by at most one truck at the same time, every truck
is used. Moreover, in the problem specification, we have several strong
constraints about the relative amounts of different types of goods stored
in a depot, the number of times a truck can visit a market, the order in
which goods should be stored, the order in which we should store some good
and buy another one, and deadlines about delivering goods once they have
been loaded in a truck.
**PLESE NOTE THAT** while we tried to generate the constraints in such a
way that the problems remain solvable, there is no guarantee that every
problem instance is solvable. Unfortunately, there is no planner that we
could use to make this check.
TPP MetricTemporalComplexPreferences
------------------------------------
The operators in this version are the same as in the MetricTemporal version.
In addition, it contains many preferences over state trajectory constraints
that are similar to those used for the MetricTemporalConstraints version.