Dynamic programming for aligning sketch maps
Technologies implemented
Python, graph matching, SARSA algorithm, TABU search, reinforcement learning, flask, anaconda environment
Abstract
Sketch maps play an important role in communicating spatial knowledge, particularly in applications interested in identifying correspondences to metric maps for land tenure in rural communities. The interpretation of a sketch map is linked to the users’ spatial reasoning and the number of features included. Additionally, in order to make use of the information provided by sketch maps, the integration with information systems is needed but is convoluted.
The process of identifying which element in the base map is being represented in the sketch map involves the use of correct descriptors and structures to manage them. In the past years, different methods to give a solution to the sketch matching problem employs iterative methods using static scores to create a subset of correspondences.
In this thesis, we propose an implementation for the automatic aligning of the sketch to metric maps, based on dynamic programming techniques from reinforcement learning. Our solution is distinctive from other approaches as it searches for pair equivalences by exploring the environment of the search space and learning from positive rewards derived from a custom scoring system. Scores are used to evaluate the likeliness of a candidate pair to belong to the final solution, and the results are back up in a state-value function to recover the best subset states and recovering the highest scored combinations. Reinforcement learning algorithms are dynamic and robust solutions for finding the best solution in an ample search space. The proposed workflow improves the outcoming spatial configuration for the aligned features compared to previous approaches, specifically the Tabu Search.
