Ph.D Thesis

Ph.D StudentDovrat David
SubjectAn Automata Theory Method for the Analysis of Unicycle
Pursuit Problems
DepartmentDepartment of Computer Science
Supervisor PROF. Alfred Bruckstein


The Pursuit Problem depicts a scenario where a target is chased by an agent, whose

movement is prescribed by some defined policy. Examples of what can be regarded as

solutions to the pursuit problem include the shape of the agent’s trajectory, whether the agent ultimately captures the target, and the circumstances of the capture, including the time required for capture to be achieved.

The Unicycle Model is a popular simplification used to describe the kinematics

of complex vehicular systems. An agent modeled as a unicycle has three degrees of

freedom: the location on the plane, and the orientation of the agent. The agent is

constrained to move only in the direction of its orientation, and only two input

signals are available to control the model: steering and speed.

A Unicycle Pursuit Problem is a pursuit problem where the pursuing agent is modeled as a unicycle.

This thesis describes a method used for solving unicycle pursuit problems by mapping the properties of the pursuit to a directed graph, which can then be regarded as

a state machine that describes the evolution of these properties in an abstract way.

The thesis details the analysis of two particular unicycle pursuit problems, to

demonstrate results that were achieved by studying the traits and structure of the

corresponding finite state machines generated by the method described here. In addition, we present a software framework used to implement a multi-agent version of one of these unicycle pursuit problems using Unmanned Aerial Vehicles (UAVs). We call this framework AntAlate. AntAlate allows software application developers to focus on their algorithms by abstracting away the UAV platform, enforcing safety measures, and providing a versatile interface for algorithm interaction.