1 of 30

Autonomous Multi Robot Shark Tracking

Kehlani Fay, Michael Giordano, Alberto Soto, Christopher M. Clark, Emily Spurgeon, James Anderson, Christopher G. Lowe

Lab for Autonomous and Intelligent Robotics

2 of 30

Motivation: Why Track Sharks

Ecologists interested in understanding shark behaviors, and the drivers behind them including:

Movement patterns

Population demographics

Habitat selection

Physiological requirements

Lab for Autonomous and Intelligent Robotics

[(Alex) Previously was thinking …] Tracking marine life is incredibly important for marine biologists in order to understand human impact on shark migration patterns, population estimates, and shark behavior. This includes understanding the impact of shark fin poachers, tracking endangered species, impacts of climate change on sharks, and of course just learning more about our oceans overall.

The original method for shark tracking was sitting on a boat for a long time and hoping to find a shark. Then if you find a shark, find some way to trap/wrestle the shark so it is still enough to put a tracker on it (some people even do surgery to implant the tracker for life), and then release it. Each tracker emits a ping which is unique to itself and monitors biological data of the shark including swim depth, temperature, and location. In order to receive information from the tag, underwater receivers need to be deployed and sharks need to swim close by them. Alternatively, some use satellite trackers which require the shark to surface to send the signal.

The goal of this work is to find alternative methods for shark tracking and receiving information from tagged sharks in hopes of making the process less human intensive and provide additional information on sharks

3 of 30

Motivation

A range of telemetry tools help gather data:

Satellite Tags

Acoustic Tags

“Smart” Packages

Lab for Autonomous and Intelligent Robotics

[(Alex) Previously was thinking …] Tracking marine life is incredibly important for marine biologists in order to understand human impact on shark migration patterns, population estimates, and shark behavior. This includes understanding the impact of shark fin poachers, tracking endangered species, impacts of climate change on sharks, and of course just learning more about our oceans overall.

The original method for shark tracking was sitting on a boat for a long time and hoping to find a shark. Then if you find a shark, find some way to trap/wrestle the shark so it is still enough to put a tracker on it (some people even do surgery to implant the tracker for life), and then release it. Each tracker emits a ping which is unique to itself and monitors biological data of the shark including swim depth, temperature, and location. In order to receive information from the tag, underwater receivers need to be deployed and sharks need to swim close by them. Alternatively, some use satellite trackers which require the shark to surface to send the signal.

The goal of this work is to find alternative methods for shark tracking and receiving information from tagged sharks in hopes of making the process less human intensive and provide additional information on sharks

4 of 30

Motivation

Standard telemetry approaches suffer poor spatial or temporal resolution

Methods to improve resolution expensive and time consuming

Some methods of tag attachment invasive

Lab for Autonomous and Intelligent Robotics

[(Alex) Previously was thinking …] Tracking marine life is incredibly important for marine biologists in order to understand human impact on shark migration patterns, population estimates, and shark behavior. This includes understanding the impact of shark fin poachers, tracking endangered species, impacts of climate change on sharks, and of course just learning more about our oceans overall.

The original method for shark tracking was sitting on a boat for a long time and hoping to find a shark. Then if you find a shark, find some way to trap/wrestle the shark so it is still enough to put a tracker on it (some people even do surgery to implant the tracker for life), and then release it. Each tracker emits a ping which is unique to itself and monitors biological data of the shark including swim depth, temperature, and location. In order to receive information from the tag, underwater receivers need to be deployed and sharks need to swim close by them. Alternatively, some use satellite trackers which require the shark to surface to send the signal.

The goal of this work is to find alternative methods for shark tracking and receiving information from tagged sharks in hopes of making the process less human intensive and provide additional information on sharks

5 of 30

Research Goals

Explore if data driven, probabilistic motion models can inform and create optimized multi-robot tracking planners

Develop trajectory plans which optimize spatial-temporal resolution and account for future shark movements

Image Credit: LAIR and Christopher Lowe

Lab for Autonomous and Intelligent Robotics

6 of 30

Prior Work - Single AUV tracking

Enabled an AUV to provide high resolution shark data over ~0.5 - 1.6 hours

Increased tracking area and on par accuracy to stationary techniques (Clark et. al 2013)

Clark, Christopher & Forney, Christina & Manii, Esfandiar & Shinzaki, Dylan & Gage, Chris & Farris, Michael & Lowe, Christopher & Moline, Mark. (2013). Tracking and Following a Tagged Leopard Shark with an Autonomous Underwater Vehicle. Journal of Field Robotics. 30. 10.1002/rob.21450.

Credit: Lin et al. 2016 (LAIR)

Lab for Autonomous and Intelligent Robotics

7 of 30

Prior Work - Multi-AUV tracking

Lin, Yukun & Hsiung, Jerry & Piersall, Richard & White, Connor & Lowe, Christopher & Clark, Christopher. (2016). A Multi-Autonomous Underwater Vehicle System for Autonomous Tracking of Marine Life: A Multi-AUV System for Autonomous Tracking of Marine Life. Journal of Field Robotics. 34. 10.1002/rob.21668.

Image Credits: Lin et al. 2016 (LAIR)

Lab for Autonomous and Intelligent Robotics

To improve localization accuracy of the prior work, a multi robot system was deployed to cooperatively track a tagged shark. This system used hydrophones to localize sharks with bearing and heading estimates. These measurements were shared between AUVs using an acoustic modem and fused with the prior work’s shark particle filter. This work deployed a full inter AUV control flow, state estimation with multiple hydrophones and AUVs, and created a smart tag to read incoming signals. The planner deployed for this work used A* and swaps between search of the shark and shark circling once the target is found. This work reduced localization error from 80 degrees to 30 and increased localization resolution from 10 meter range to an accuracy of 1-3 meters. However, this work did not take into account uncertainty in shark measurements for planning or future positions of the shark based on the collected data which resulted in sometimes losing the found shark. In hopes of extending run times from under an hour, our planner builds upon this prior work using behavioral models to create a new motion planner which accounts for potential future shark positions.��Building off this prior work, our work plans to use the same state estimation, system framework, and hydrophone setup when deploying to real robots in future work.

8 of 30

Prior Work - Multi-AUV archeology

Creates a coupled and decoupled RRT planner for information gain of site reconstruction

Utilizes merit-based token passing to bid for updated plans

Wu, Jane & Bingham, Russell & Ting, Samantha & Yager, Kolton & Wood, Zoë & Gambin, Timmy & Clark, Christopher. (2019). Multi‐AUV motion planning for archeological site mapping and photogrammetric reconstruction. Journal of Field Robotics. 36. 10.1002/rob.21905.

Image Credit: Wu et al. 2019 (LAIR)

Lab for Autonomous and Intelligent Robotics

9 of 30

Problem Statement

Given N identical AUVs, each equipped with hydrophone sensors, maximize the likelihood of a target being successfully tracked over t seconds

Subgoals:

Maximize likelihood target stays in a symmetrical formation
Minimize chance AUV comes in too close contact with a shark
Minimize chance AUVs go to far from a shark and can’t read shark info
Adapt quickly to new information

Lab for Autonomous and Intelligent Robotics

10 of 30

Overview

Shark data collection

Motion Models & fitness

Algorithm

Simulation Results

Lab for Autonomous and Intelligent Robotics

11 of 30

Data Collection [James]

James Anderson

Lab for Autonomous and Intelligent Robotics

12 of 30

Motion Data

Lab for Autonomous and Intelligent Robotics

13 of 30

Motion Data

Heading change in radians

1 minute position change by velocity groups

Lab for Autonomous and Intelligent Robotics

14 of 30

Probability Distribution

For every cell, the probability of a shark being at that location is updated via Markovian expansion:

Where probability is between [0,1] at t

Probability Model of Future Positions with Normalized Headings

Lab for Autonomous and Intelligent Robotics

From this data we concluded velocity and current heading mattered most for determining the future position of the shark. Depth, temperature, and similar variables analyzed were found to be negligible.

Using this 2D grid structure, we update the location of the shark as a probability distribution. The probability of the shark existing at cell (i,j) is calculated by taking the sum of the chance a shark is at all of the previous cells times the probability the shark will transition to that cell. The transition filters are determined based on the random sampled velocity grouping from the data acquired above. The orientation filter applied is a random sample from the roughly normal distribution determined from the orientation data prior. After extracting the updated shark’s position, the shark matrix is updated for the planner and the multi robot algorithm runs with the updated shark position.

15 of 30

Fitness Function

= probability of shark

Lab for Autonomous and Intelligent Robotics

From this data, the authors developed a fitness function to evaluate each node for the multi-robot algorithm represented in equation 2. Once a trajectory reaches the desired time length, the full trajectory is evaluated in equation 1. This value is used to pick the most optimal trajectory for all robots. Equation 1 takes in this complete list of nodes containing all robot states and weights future node scores proportional to the total trajectory time. This allows for higher weighting of robot locations later on in order to put the formation in an ideal location for further planning. Please note a node in this formulation is the state of each AUV at time t.

To evaluate each node, equation 2 is used. Through iterating over every grid cell pair (i,j) and robot pair (r_u, r_v), the planner calculates the fitness as the sum of the probability of the shark location at the grid cell i,j , multiplied by the robot formation evaluation seen as function C(), and D() is the resulting weight from the relative distance between the selected robot and the shark.

16 of 30

Fitness Function

= probability of shark

= AUV-shark angle value

Lab for Autonomous and Intelligent Robotics

From this data, the authors developed a fitness function to evaluate each node for the multi-robot algorithm represented in equation 2. Once a trajectory reaches the desired time length, the full trajectory is evaluated in equation 1. This value is used to pick the most optimal trajectory for all robots. Equation 1 takes in this complete list of nodes containing all robot states and weights future node scores proportional to the total trajectory time. This allows for higher weighting of robot locations later on in order to put the formation in an ideal location for further planning. Please note a node in this formulation is the state of each AUV at time t.

To evaluate each node, equation 2 is used. Through iterating over every grid cell pair (i,j) and robot pair (r_u, r_v), the planner calculates the fitness as the sum of the probability of the shark location at the grid cell i,j , multiplied by the robot formation evaluation seen as function C(), and D() is the resulting weight from the relative distance between the selected robot and the shark.

17 of 30

Fitness Function

= probability of shark

= angle value

= distance function

Lab for Autonomous and Intelligent Robotics

From this data, the authors developed a fitness function to evaluate each node for the multi-robot algorithm represented in equation 2. Once a trajectory reaches the desired time length, the full trajectory is evaluated in equation 1. This value is used to pick the most optimal trajectory for all robots. Equation 1 takes in this complete list of nodes containing all robot states and weights future node scores proportional to the total trajectory time. This allows for higher weighting of robot locations later on in order to put the formation in an ideal location for further planning. Please note a node in this formulation is the state of each AUV at time t.

To evaluate each node, equation 2 is used. Through iterating over every grid cell pair (i,j) and robot pair (r_u, r_v), the planner calculates the fitness as the sum of the probability of the shark location at the grid cell i,j , multiplied by the robot formation evaluation seen as function C(), and D() is the resulting weight from the relative distance between the selected robot and the shark.

18 of 30

Fitness Function - Relative Heading

= relative heading between robot,r, and shark, s

= difference actual and optimal spread with N AUVs

= reward for AUV headings with averaged differences between AUVs��

Lab for Autonomous and Intelligent Robotics

19 of 30

Fitness Function - Distance function

Lab for Autonomous and Intelligent Robotics

20 of 30

MRMP Algorithms

Independent State Planner

Each robot state is planned from the prior robot’s state

Joint Expansive Planner

Robot states are planned around a central point and robot’s prior state

Node Definitions:

Lab for Autonomous and Intelligent Robotics

In order to take advantage of future shark locations and the fitness function developed prior, the authors proposed two variants of RRT. These two variants are Independent and Joint Expansive Planners. Each planner takes in the shark’s information and generates kinodynamically feasible, collision free trajectories based on the physical limitations of the robot and the shark’s predicted movement. We assume when deployed to real world that communication strategies of prior our lab’s prior work with token passing and updating each robot’s location iteratively and until the robot passes it’s updated state it will plan from it’s originally calculated trajectory. Additionally, we build from our lab’s prior work through extending the multi-agent collision checker.

A main difference between these two planners are their coordination strategy. For the Individual planner, a node is defined as the time stamp, and all of the robots locations, the fitness of the node, and the parent. For the joint planner, the node contains the same information along with the center of the robot cluster Xc. The joint planner expands from the center of the cluster and recalculates each of the robots positions while checking to make sure each robot has not exceeded its max velocity given its initial starting and end location. If it does, the velocities of all robots are scaled such that no v_max exceed any robots.

21 of 30

Algorithm(s)

Lab for Autonomous and Intelligent Robotics

Both planners can be explained through a slightly abstracted algorithm where NodeExpansion is a different function for each of the planners. First we start with an initial node containing the start locations of each robot at t=0. Then while the plan time is less than the budgeted or allotted time, we grab a random node from the tree, expand from that node, and check if the new expansion is collision free. If it is collision free, we also check for high fitness, meaning the fitness of the node is above our set threshold of .8. In practice this significantly improved our planner fitness scores from around .15 to .8 or .9.

After meeting this criteria and checking if collision free from obstacles and other robot’s paths, the node is added to the tree and checked if the total trajectory of that node is at the desired trajectory time length. If it does, it is considered in the end game state and the fitness for the whole trajectory is calculated. This repeats until the budgeted time runs out.

22 of 30

Algorithm(s) Expansions

ISE and JSE:

JSE Only:

Lab for Autonomous and Intelligent Robotics

Both planners start by randomly getting a change in velocity between delta v of the robot of + or - .25 m/s, and a random change in angular velocity of + or - 15 degrees due to the Iver3s set abilities. As all robot’s start from the same random seed and calculate each expected robot in the same order, these numbers are the same across robot to robot without communication. Only states and central location are communicated. Each planner first caclulates a linear expansion with the new desired velocity, angular velocity, and heading.

Both planners then calculate an arc expansion seen in equation 6 which generates an arc for each robot. Doing a tangent and arc in sequence was found to result in higher scores than all other combinations. These two functions then store two nodes, one for the linear expansion and another for the arc expansion.

For the joint planner, these calculations are applied to the central point instead of each robot. The joint planner then recalculates the distance of the remaining robots positions around the cluster to determine ideal placement of each robot (equations 9-11). The joint planner does additional velocity checking for robots on outside of turns do not exceed the max velocity or change in velocity in order to ensure v_max is not exceeded. If it is beyond the robot’s limit, expansion with v_max is used instead from the robot’s prior state.

23 of 30

Algorithm - Individual

Total end fitness: 0.84

Total end fitness: 0.86

Lab for Autonomous and Intelligent Robotics

Here are some visualizations of the results of the Individual Planner. These are two examples of the planner solving the same setpu in different ways. On the left, the planner has one robot go around an obstacle in order to avoid coming to close to the shark. On the right, the robot represented in blue stalls in order to allow the other three robots through and then catches up with the group. Although our work is designed for primarily open sea with fea obstacles beyond coastline and a rocks, it was nice to see the algorithm could work in slightly more obstacle dense situations. While it appears the robots come quite close to the obstacles, this is due to scale of the graphs. The buffer range applied to the collision free planner was 3 meters for the examples above. The graphs are 100 by 170 meter scale above. However, these graphs are under overly ideal conditions where the shark passed through the start of the robot cluster. These would be the ideal conditions once the shark is found. Next are some alternatives without this condition during search.

24 of 30

Algorithm - Individual

Total end fitness: 0.73

Robot Origin: (-40, 40)

Shark Start: 0,0

Total end fitness: 0.74

Robot Origin : (25, 40)

Shark Start: 0,0

Total end fitness: 0.91

Robot Start : (0, 0)

Shark Start: 0,0

Probability Distribution

Robot Origin: robots spaced evenly around start (+/- 15 meters from this location)

Lab for Autonomous and Intelligent Robotics

Comparing two situations where robots start from above and behind the shark at 40 meters behind and 40 meters above in graph 1. It is able to catch up with the shark which averages ~.75 m/s but has changing velocity throughout the run. Graph two shows the same setup with a different starting location of right before an obstacle. Starting at below the shark at 40 meters south and 25 meters ahead, the robots are able to stall to have the shark catch up while they get into formation. Finally the graph on the far right show under the ideal conditions again of being centered around the shark but with displays the probability distribution the robots are using to inform their plan in red. Red represents a high probability of the shark. The plots above show only branch pairs with a fitness above .7. Resulting in less branches being displayed than the prior slide.

For sake of time, we will not show joint. Please see our paper for details.

25 of 30

Result Comparison

Lab for Autonomous and Intelligent Robotics

26 of 30

Result Comparison

Lab for Autonomous and Intelligent Robotics

27 of 30

Discussion

Probabilistic behavioral models can be used to inform motion planning using probabilistic rewards

Expanding from high fitness worked well along with more similar predicted to actual models

Lab for Autonomous and Intelligent Robotics

28 of 30

Future Work

Future work to deploy on IVER3s and test with tagged sharks

Compare against prior multi-robot planner which only used current shark states from real world experiments

Compare with Levy Flight shark models to Markov and ability to work with multiple distributions / sharks

Test communication and ability to work without perfect communication and with some missing shark updates

Lab for Autonomous and Intelligent Robotics

29 of 30

Acknowledgements

CSULB SharkLab:

Shark Data - Christopher Lowe

Emily Spurgeon, James Anderson

Honorary Biologist - Alberto Soto

Research Advisor

Christopher M Clark

Michael Giordano

Harvey Mudd College

Lab for Autonomous and Intelligent Robotics

30 of 30

Autonomous Multi Robot Shark Tracking

Kehlani Fay, Michael Giordano, Alberto Soto, Christopher M. Clark, Emily Spurgeon, James Anderson, Christopher G. Lowe

Lab for Autonomous and Intelligent Robotics