Date of Award

May 2020

Degree Type

Thesis

Degree Name

Master of Science

Department

Computer Science

First Advisor

Amol Mali

Committee Members

Ichiro Suzuki, Christine Cheng

Keywords

Geometric median, Robot motion planning

Abstract

Service robots are becoming increasingly common, and businesses are adopting their use at an increasingly rapid rate in order to reduce costs and provide efficiencies in performing mundane tasks. However, very little research has been performed in order to understand and address ethical concerns regarding their deployment and use.

One such concern is how one can ensure placement of a service robot such that is does not discriminate either in favor of or against individuals. This research explores techniques that can be used to provide a quantitative methodology to ensure fairness in terms of service robot placement such that discrimination does not occur.

These techniques include the development and further enhancement of a heuristic hill climbing algorithm used to approximate the Geometric Median (GM). This algorithm is then benchmarked against Weiszfeld’s Algorithm, a well-known algorithm commonly used to solve the GM problem.

iii

These two algorithms are then visualized using Dynamics Explorer, an open source software tool, to create 2d maps of the dynamics of their convergence rates along with maps of F(), the “sum of the Euclidean distances” function underlying the calculations used by both GM approximation algorithms.

The heuristic hill climbing algorithm is also extended to handle obstacles being introduced into the service robot’s workspace.

It is further shown that as the size of ξ approaches ∞+, the Geometric Median converges to the centroid, given certain assumptions, such as the target points being evenly distributed in the plane.

Download

Share

COinS