Loading...
 

Multi-Zeno


Presentation


ZenoSolver is a C++ software dedicated to generate and exactly solve MultiZenoTravel instances. Firstly, it allows to tune every parameters in order to adjust the difficulty or to obtain different shapes of Pareto Fronts.
Second, ZenoSolver outputs the corresponding PDDL (Planning Domain Definition Language, universally used now in AI Planning to describe domains and instances) that can be directly used by any standard AI planner.

Access and build


Git repository of this project is available anonymously through the following command:

git clone https://gforge.inria.fr/git/zenosolver/zenosolver.git


Install g++ and CMake.

In a terminal, assuming you are in the ZenoSolver root folder:

mkdir build && cd build cmake .. make


By default ZenoSolver is built in the release mode, with all possible optimizations. To activate the debug build, in the build folder, use:

cmake .. -DCMAKE_BUILD_TYPE=DEBUG make

Usage


The main (required) parameters to describe a MultiZeno instance are given by -p,-t and -n, respectively the number of planes, passengers and cities.

ZenoSolver proposes two ways to generate costs and durations, namely by a datafile and using generating functions.

Using a file

This simpliest way is to provide costs and durations through a text file using option -d.


Using a generating function

The second option is to provide two generating functions, one for the costs and one for the durations.
To do so, the options are -C for the costs and -D for the durations.

We provide five basics generation function as described in the following table:
function
1log(i)
2sqrt(i)
3i
42^i
55*(i / 2) + 0.1*(i mod 2)


As functions are hardcoded, using your own functions requires either to edit functions in src/genFunctions.cpp or to write your own in the same file and modify the switch in src/solver.cpp. Of course, you must recompile.

To adjust the front, we provide some constants. The effective cost and duration for the city i is obtained with the following formulas:

c_i = x*g(j*i+k) + y
d_i = x*f(l*i+m) + y

Option -x and -y are share by both while -j,-k,-l and -m belongs to one or the other generation function.


Other options

As experimentally proved, the pruning can degrade performances (mainly with concave generating functions).The flag -a switches off the pruning method.

The larger the beta value, the slower the algorithm will be since the number of iterations by PPP explodes. By limiting the beta value, we give up on the exact front but considerably decrease the CPU time. Experimentations shown, depending on the instance, that the returned front can remain really close to the the exact front.
To limit the beta value to a particular value, use the flag -B.

As ZenoSolver handles only integers for costs and durations, it will cast generated vectors (or provided data) to integers. The adjustement factor (option -r) is a multiplicative constant in order to avoid some errors (for instance, obtaining more than once the same value because log(i) and log(i+1) have same floor value).
By default it is set to 1 but a better value for most of functions could be 100.

Output

The option -G will generate the corresponding PDDL file. To provide a custom name, specify the option -Q.

More information can be found by using ./zenoSolver -h.

MultiZeno Instances Sample


To download all PDDL files, Pareto Front and Instances description, click here .


Image

Instance 1
Cities20
Passengers6
Planes2
Pareto Front409

PDDL File
Pareto Front






Image

Instance 2
Cities150
Passengers3
Planes2
Pareto Front1496

PDDL File
Pareto Front






Image

Instance 3
Cities250
Passengers3
Planes2
Pareto Front2197

PDDL File
Pareto Front






Image

Instance 4
Cities3
Passengers21
Planes2
Pareto Front61

PDDL File
Pareto Front






Image

Instance 5
Cities100
Passengers3
Planes2
Pareto Front268

PDDL File
Pareto Front






Image

Instance 6
Cities200
Passengers3
Planes2
Pareto Front538

PDDL File
Pareto Front






Image

Instance 7
Cities8
Passengers26
Planes25
Pareto Front15

PDDL File
Pareto Front






Image

Instance 8
Cities200
Passengers3
Planes2
Pareto Front399

PDDL File
Pareto Front






Image

Instance 9
Cities10
Passengers10
Planes3
Pareto Front383

PDDL File
Pareto Front