This June, I successfully defended my bachelor thesis at Charles University. During the spring semester, I spent countless hours working on my thesis on the topic “Planning for Transportation Problems”. Let me explain in several steps, what the thesis attempts to solve.

Picture: TransportEditor showing an example Transport problem.

Automated planning is a field of artificial intelligence, that deals with designing sequences of actions for intelligent agents with respect to some objective. Specifically, in my thesis, intelligent agents correspond to trucks delivering packages to their destinations in a road network (for a more precise definition, see Chapter 2). Planning (and scheduling) rely heavily on more theoretical fields like combinatorial optimization, reinforcement learning, or combinatorial search (Chapter 1).

Several variants of the mentioned problem were discussed and solutions to some were proposed. Specifically, we focused on datasets used at the International Planning Competition (IPC)) for the “Transport” planning problem. We propose several domain-specific (customized for the “Transport” problem) algorithms for devising plans, i.e. sequences of “drive”, “pick-up package”, and “drop package” actions for vehicles.

Leveraging knowledge about our problem, we managed to beat almost all competing domain-independent (not “Transport”-specific) planners. For detailed results, see Chapter 6. Our approach shows that such knowledge can be effectively incorporated into known planning techniques, and successfully used to create better plans, and create them faster.

To visualize our work, we developed TransportEditor, a desktop GUI application for viewing and creating Transport problems and solving them using external and embedded planners.

Video: Demo of an older version of TransportEditor.

TransportEditor was presented at the System Demonstrations and Exhibits track at the International Planning and Scheduling Conference (ICAPS) 2017 in Pittsburgh, USA. The paper can be read here.

In the meantime, I graduated from Charles University, and after a great summer that I spent interning at Google in Munich, I am now studying at ETH Zurich in Switzerland (more on that in a followup post).

Slides from the presentation.