<p> In this
thesis, we investigate and characterize policies for task allocation to teams
of agents in settings with heterogeneity and risk. We first consider a scenario
consisting of a set of heterogeneous mobile agents located at a base (or
depot), and a set of tasks dispersed over a geographic area. The agents are
partitioned into different types. The tasks are partitioned into specialized
tasks that can only be done by agents of a certain type, and generic tasks that
can be done by any agent. The distances between every pair of tasks are
specified and satisfy the triangle inequality. Given this scenario, we address
the problem of allocating these tasks among the available agents (subject to
type compatibility constraints) while minimizing the maximum travel cost for
any agent. We first look at the Heterogeneous Agent Cycle Problem (HACP) where
agents start at a common base (or depot) and need to tour the set of tasks
allocated to them before returning to the base. This problem is NP-hard, and we
provide a 5-approximation algorithm. We then consider the Heterogeneous Agent
Path Problem (HAPP) where agents can start from arbitrary locations and are not
constrained to return to their start location. We consider two approaches to
solve HAPP and provide a 15-approximation algorithm for HAPP.</p>
<p> We then
look at the effect of risk on path planning by considering a scenario where a
mobile agent is required to collect measurements from a geographically
dispersed set of sensors and return them to a base. The agent faces a risk of
destruction while traversing the environment to reach the sensors and gets the
reward for gathering a sensor measurement only if it successfully returns to
base. We call this the Single Agent Risk Aware Task Execution (SARATE) problem.
We characterize several properties of the optimal policy for the agent. We
provide the optimal policy when the risk of destruction is sufficiently high
and evaluate several heuristic policies via simulation. We then extend the analysis
to multiple heterogeneous agents. We show that the scoring scheme is submodular
when the risk is sufficiently high, and the greedy algorithm gives solutions
that provide a utility that is guaranteed to be within 50% of the optimal
utility. </p>
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/12689666 |
| Date | 29 July 2020 |
| Creators | Amritha Prasad (9153848) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/thesis/Heterogeneity-_and_Risk-Aware_Algorithms_for_Task_Allocation_To_Mobile_Agents/12689666 |
Page generated in 0.0051 seconds