Dmitry Boulytchev

Anton Moscal

Eugene Vigdorchick

We all are from the Mathematics & Mechanics Faculty of St.Petersburg (Russia) University.

Here is the our group home page.

For contest we are used computers of the IntelliJ Software, which currently is employer of two from us (Dmitry Boulytchev and Eugege Vigdorchik). Thanks, IntelliJ.

You can download our last submission here.

The results are following:

Simple:		8258
Hairpins:		12800
Sepang:		14971
EatYouAlive:		14496
Car:		5650
IcfpContest:		4956
Gothenburg:		3400
ManyWays:		7599
PhilAndSimon:		6600
TOTAL:		78730
Rally:		37195
Een:		8069

The sources organized as follows:

• README -- README file
• sim.ml -- algorithm body
• simulator.[ch] -- C runtime (includes fixed poin arith. and step calculator)
• Makefile
• util/
  • executor.ml -- trace simulator
  • optimizer.ml -- tiny optimizer
  • painter.ml -- track reducer
  • dijkstra.ml -- Dijkstra's shortest path algorithm
  • morda.ml -- and graphic interface for it
  • simulator.[ch], sim.ml, trace.ml --- parts of ../sim.ml

Since we didn't manage to find any proven-optimal algorithm we've used search-and-cut strategy flavoured with miscellaneous heuristics.

The algotrithm look like this:

1. Choose any state (x, y, v, d, t) from an active set.
2. For each operation (a., l., r. etc.) apply it to choosen set N times (actually we use different N's from 50 to 150).
3. Filter obtained set of states.
4. Repeat until goal is reached.

This is a screenshot of the process:

Initially active set consists of starting state.

Some heuristics used to cut the active set:

1. States are ordered by distance to goal.
2. States behind some distance from "leader" are cutted.
3. If we got state with coordinates, speed and direction close to one of "earliest" states then "new" state is dropped.

Some adaptive features are introduced: "closeness" criteria strengthens near the bounds of track, distance from the "leader" is reduced when active set become too large and increased if active set become too small.

Two optimizations are performed:

• After first algorithm run the track is reduced to some neihbourghood of resulted trajectory and algorithm repeats with harder parameters.

  

  This is a screenshot of the "restricted" trace #8

• Resulted trace optimized: sequence of rolls changed to accelerate-brake sequence, left-right turns changed to roll.