Back to search

Boston University

Robust localization and navigation with linear programming

Abstract

dc:description.abstract

Linear programming is an established, well-understood technique optimization problem; the goal of this thesis is to show that we can still use linear programming to advance the state of the art in two important blocks of modern robotic systems, namely perception, and control. In the context of perception, we study the effects of outliers in the solution of localization problems. In its essence, this problem reduces to finding the coordinates of a set of nodes in a common reference frame starting from relative pairwise measurements and is at the core of many applications such as Structure from Motion (SfM), sensor networks, and Simultaneous Localization And Mapping (SLAM). In practical situations, the accuracy of the relative measurements is marred by noise and outliers (large-magnitude errors). In particular, outliers might introduce significant errors in the final result, hence, we have the problem of quantifying how much we should trust the solution returned by some given localization solver. In this work, we focus on the question of whether an L1-norm robust optimization formulation can recover a solution that is identical to the ground truth, under the scenario of translation-only measurements corrupted exclusively by outliers and no noise. In the context of control, we study the problem of robust path planning. Path planning deals with the problem of finding a path from an initial state toward a goal state while considering collision avoidance. We propose a novel approach for navigating in polygonal environments by synthesizing controllers that take as input relative displacement measurements with respect to a set of landmarks. Our algorithm is based on solving a sequence of robust min-max Linear Programming problems on the elements of a cell decomposition of the environment. The optimization problems are formulated using linear Control Lyapunov Function (CLF) and Control Barrier Function (CBF) constraints, to provide stability and safety guarantees, respectively. We integrate the CBF and CLF constraints with sampling-based path planning methods to omit the assumption of having a polygonal environment and add implementation to learn the constraints and estimate the controller when the environment is not fully known. We introduce a method to find the controller synthesis using bearing-only measurements in order to use monocular camera measurements. We show through simulations that the resulting controllers are robust to significant deformations of the environment. These works provide a simple approach in terms of computation to study the robustness of the localization and navigation problem.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Systems Engineering
Grantor
Boston University
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bahreinian, Mahroo
Advisor dc:contributor.advisor
  • Tron, Roberto
ORCID dc:identifier.orcid

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/45459

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Bahreinian, Mahroo. Robust localization and navigation with linear programming. doctoral thesis, Boston University, 2023. https://hdl.handle.net/2144/45459