"Interactive multi-objective path planning algorithm for accessible sidewalks"

Bachelor Thesis by Alisa Todorova

Context

This thesis was prepared in partial fulfilment of the requirements for the Degree of Bachelor of Science in Data Science and Artificial Intelligence, Maastricht University. This research was done in the context of a research internship at the Urban Innovation and R&D department of the City of Amsterdam. The motivation behind my research is to make Amsterdam more accessible. The end goal of the big project that my research is part of, is to create a highly user-dependent app for Amsterdam citizens with mobility issues and those who use assistive devices (i.e., wheelchairs, strollers, canes). This app should find the user the most accessible sidewalks, with respect to their specific needs.

I propose a new method that leverages the power of Gaussian Processes and an interactive approach to quickly generate likely preferred solutions (i.e., paths) without computing the entire Pareto Front.

Abstract

This paper addresses the multi-objective shortest path problem (MOSPP) in a transportation routing setting. The goal of much research on MOSPPs has been on computing the full Pareto set, i.e., the set containing all possible optimal solutions (i.e., Pareto-optimal paths) which have different optimal tradeoffs (i.e., best compromises) between the given objectives. We propose an algorithm which finds a Pareto-optimal path for each individual user without having to compute the entire Pareto front. Our algorithm consists of two parts: an outer-loop, which helps us select a target region (i.e., a part of value space that is likely to contain possible value vectors (and their associated paths) preferred by the user), and an inner-loop, which finds a path from that target region. We test our algorithm on a map of Amsterdam. Our algorithm always finds a Pareto-optimal path that lies in the target region.

Installation

1. Download and extract the zip file.
2. Install all dependencies:

 pip install -r requirements.txt

3. Runexperiments

How it works

1. outer-loop: Selects a target region, in which we search for new paths that have likely preferred value vectors
2. inner-loop: Finds paths with value vectors in the target region. My approach is depth-first search (DFS) algorithm, guided by the lower bounds for each objective for each node, obtained from the single-objective value iteration.
3. multi-objective value iteration: Computes the full Pareto front

Usage

1. To run multi-objective value iteration:

pvi_result = pvi(G, T, ('length', 'crossing'))

2. experiments: Running different experiments of my proposed algorithm.
3. full map: Full map with radius of 800m, centered around the Rijksmuseum (11401 nodes)
4. small map: Small map with radius of 250m, centered around the Rijksmuseum (1006 nodes)

Acknowledgements

1. In outer-loop, we use the Gaussian process and Acquisition function as blackboxes from "Ordered Preference Elicitation Strategies for Supporting Multi-Objective Decision Making" by Luisa M. Zintgraf, Diederik M. Roijers, Sjoerd Linders, Catholijn M. Jonker, and Ann Nowé, which was published at AAMAS (Autonomous Agents and Multi-Agent Systems), Stockholm 2018. GitHub link.
2. In multi-objective value iteration, for Prune we follow the methods pareto_dominates, p_prune and pvi from Roijers, D. M., Röpke, W., Nowe, A., & Radulescu, R. (2021). On Following Pareto-Optimal Policies in Multi-Objective Planning and Reinforcement Learning. Paper presented at Multi-Objective Decision Making Workshop 2021. Link to paper and GitHub link.