Human navigation in a multilevel travelling salesperson problem
Loading...
Authors
Author (Corporation)
Publication date
22.01.2022
Typ of student thesis
Course of study
Collections
Type
05 - Research report or working paper
Editors
Editor (Corporation)
Supervisor
Parent work
Special issue
DOI of the original publication
Link
Series
Series number
Volume
Issue / Number
Pages / Duration
Patent number
Publisher / Publishing institution
PsyArXiv
Place of publication / Event location
Ithaca, NY
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
Finding the optimal tour that visits a series of locations sequentially, such as going for errands, is an everyday task formally known as the travelling salesperson problem (TSP). In this article we focus on the understudied type of multilevel or M-TSP, which take place in a multilevel environment, like a building. In a TSP, the number of alternative tours the decision-maker needs to consider is given by the factorial of the locations to visit; hence a 3-target TSP has 6 alternatives and a 12-
target TSP has 479 million. Considerable research has focused on combinatorial optimisation algorithms for TSPs, and in the cognitive sciences there has equally been a sustained interest on how various foraging species and humans achieve remarkably optimal performance. However, research has primarily studied planar environments, and it is unclear how people will combine horizontal and vertical spatial information to make navigational decisions in a multilevel TSP.
In this study, we asked 41 participants to first learn the locations of 12 shops (targets) in a multilevel building, and then complete a structure mapping task and two open 8-target M-TSP tasks (more than 40.000 alternatives). Using bayesian methods for mixed effects modelling, we show that human performance in navigational M-TSPs is lower than this of Euclidean TSPs, and we differentiate between the choice of tour (visit sequence) and transitions (local wayfinding). Our results show an effect of horizontal versus vertical learning. We also found that performance in navigational TSP are a composite of global and local decision making, and the people adaptively employ a path-based, rather than euclidean, measure of distance when this is ecologically relevant.
Overall we provide multiple sources of evidence for the horizontal bias theory both in mental representations and wayfinding behaviour. This study contributes to current knowledge of mental representations 3D space and is the first huto provide human data on an multilevel TSP. More generally, these findings have implications for our understanding of wayfinding and navigational behaviour in multilevel environments.
Keywords
Navigation, Travelling salesman, Spatial decision making
Subject (DDC)
600 - Technik, Medizin, angewandte Wissenschaften
Event
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
ISSN
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Preprint
Review
No peer review
Open access category
License
Citation
MAVROS, Panagiotis, Michael VAN EGGERMOND und Christoph HÖLSCHER, 2022. Human navigation in a multilevel travelling salesperson problem. Ithaca, NY: PsyArXiv. Verfügbar unter: https://doi.org/10.26041/fhnw-5788