Multi-Criteria Route Planning with Emphasis on Geospatial Result Diversity (Thesis Project)


Abstract: People travel all the time, whether it be commuting, weekend bike trips or transportation of goods. We often require our smartphones or computers to find the quickest route for us to get somewhere. But what if we are not interested merely in the shortest or the fastest option and, instead, desire to choose from several alternatives that meet our expectations in a whole range of criteria? We know that searches accommodating multiple preferences simultaneously often find an excessive number of results, the ultimate selection from which may be awkward. We therefore consider the options for reducing the solution set’s size. Our intention is to identify a few representative solutions that exhibit spatial diversity. To accomplish this, we design a multi-criteria algorithm that integrates the preference of geographically distinct solutions directly into the search, and we compare it with the method that simply filters the complete set of solutions based on their distinctness. We perform the evaluation on the road networks of the city of Prague and New York City. The proposed search algorithm indeed finds a set of routes with a convenient size, still covering all of the interesting route segments. The evaluation also shows that it is on average up to two times worse in terms of runtime, although there are certain cases in which it clearly outperforms the filtering method.

Implementation: Java


Solving Nonograms Using an Evolutionary Algorithm on GPU


Description: An evolutionary algorithm implemented to run in parallel on an nVidia GPU, solving nonogram puzzles. Since the project assignment required to use the low-level CUDA API only, no libraries or templates were utilized in the implementation. The various memory types available on the GPU were made use of to increase the performance.

Implementation: C++, CUDA

Evolving Neural Network for a Minimally-Cognitive Agent


Description: Implementation of an agent controlled by a continuous time recurrent neural network (CTRNN). The agent can move horizontally on the floor of an arena and sense the shadows of the falling objects (not their distance from the floor, however). It must evolve the ability to avoid those that are larger than itself (by gauging the size of the objects) and catch the rest (for that a proper alignment with the falling object is necessary). The CTRNN controlling the agent is evolved by a custom evolutionary algorithm.

Implementation: C#, WinForms


Evolving Neural Network for a Flatland Agent


Description: Implementation of an evolving neural network used as a controller for an agent that moves about in a simple 2D environment trying to collect as much food as possible (within a restricted number of steps) while avoiding poison. The agent has sensors for detecting what the adjacent cells contain.

Implementation: C#, WinForms


Swarm Behavior in Webots


Description: Implementation of a controller based on the Brooks subsumption architecture, creating a decentralized system invoking a group behavior through simple mechanisms. The controller controls individual robots, called e-pucks, in an environment with a bigger box that is required to be pushed by the e-pucks to one of the walls (a collective effort is necessary to move the box). The e-pucks can interact with the environment using proximity and IR sensors, and two wheels as actuators.

Implementation: C, Webots