Title

Optimisation and Simulation of the LinGraph Planner for Massive Multi-agent Systems

Description

One of the classic branches of planners is GraphPlan. The planning problem is perceived as an expanding graph which can be solved by different approaches. This idea led to the creation of LinGraph which formulates a planning problem by generating a graph with integer constraints. The graph construction together with the constraints leads to formulas resulting in a Constraint Satisfaction Problem (CSP). It is solved by using CSP-solvers such as Minion or solvers contained in Google’s OR-Tools. LinGraph is based on the linear graph planning logic (LGPL), a subset of intuistic linear logic. Similar to Petri Nets, it works by consumption of resources and generation of new resources to be able to calculate linear logic formulas.

The goal of the thesis lies in investigating different optimisation strategies as well as simulating the planner output.

Requirements

Experience with planning algorithms desirable, CSP / linear logic helful

Person working on it

Allan Grunert

Category

Master thesis