Predators@Cal

Bio-mimemtic swarm robotics are an emerging field of autonomous robotics that hold potential use cases in disaster exploration, surveillance, and navigation. In particular, ground-based robots like the TurtleBot, which are limited to essentially 2D movements, face interesting challenges in navigating unknown, irregular, or hostile environments.

One option to solve these problems is modeling them through predator-prey dynamics. In this model, we can design our robots (the "prey") to optimally survive when facing unknown dangers ("predators") in an unknown environment, much like how animals do in the wild. Some examples of real predator avoidance techniques can be seen below:

Of the above options, we chose to implement avoiding detection (like hiding behind obstacles or moving away from the predator's field of view), safety in numbers (herding), and job specialization (creating independent prey robots that can all perform different tasks).

Problem Statement

More specifically, we can define the tasks to accomplish as:

Explore as much of the map as possible (this can be quantized if we break the map into a 2D grid)
Dynamically sense and respond to its local environment (obstacles)
Collaborate in a robotic swarm to respond to global threats (predators)

We also set the following constraints:

The map should not be known beforehand (it must be generated on the fly)
Prey robots should convey minimal information to each other (for example, prey should only be able to know where another animal is by directly observing it, instead of through a shared communication channel like ROS topics)
Predator dynamics are unknown to the prey, beyond basic physical constraints (see constraint #4. This prevents us from using game theory approaches to find the optimal approach.
Predators have a limited field of view
Predator speed is limited, and predators should also be identifiable from all sides. (This is more an implementation constraint rather than a design constraint, since our camera can only accurately localize a predator if it's moving slow enough to prevent blurring)

Success Metrics

We have two main success metrics for our project: how much of the map is explored and how dangerous the prey swarm's movements are based on where the predators are. The first can be easily quantized by dividing the map into a 2D grid, but the second requires more enumeration:

where β is a tuneable parameter, R is the set of prey robots (with length N_R), P is the set of predators (with length N_P). Fundamentally, this metric allows us to get a sense for how much danger each prey robot faces based on how close they are to every predator.

This is our design pipeline, going from initial setup to sensing to navigation to controls.

Implementation of Environment Perception

To implement our design, we used a set of TurtleBot v2’s running ROS v1. Each robot was equipped with a Microsoft XBox Kinect v2. The Kinect v2 gives good data roughly within a 80x50 degree field of view, which was quite reasonable for our application. We were able to detect AR tags (predators) reliably up to about 3 meters. This visibility did decrease in narrow or cluttered environments, however, where we found visibility dropping to 1-2 meters.

Simultaneous Locationing and Mapping (SLAM)

The first step of the process is mapping the environment, which we implemented using the ROS package gmapping. This allowed us to simultaneously locate the TurtleBot within the environment while creating a cost map, which we use later for path planning. Below you can see an example of what these maps look like, both for the real robot and within a simulation.

Computer Vision

To abstract away the predator dynamics, we used an AR tag generated by the ROS package ar_track_alvar in place of real predator robot. This gave us robust and fast predator detection, but we needed to perform some additional computer vision on our Kinect output to accurately locate our AR tag in dynamic environments.

One of the first limitations we encountered was that the Kinect was fairly slow at taking pictures. It can only capture 30 FPS, which predators moving 3 meters away can only move roughly 0.33 m/s without blurring over more than ~5 pixels in the image. To fix this issue, we convolved a kernel function over the image to sharpen its edges, which as shown below improves the image quality enough for the ar_track_alvar to detect it at almost 5x the speed (1.65 m/s)!

The second limitation we encountered was in post-processing the frontier points received from the Kinect's depth sensor. There were simply too many points, creating long computation times and making the system very sensitive to noise. To solve this, we adapted a mean shift clustering algorithm for our approach. Mean shift clustering is an advanced clustering technique that does not require knowledge on the shape of cluster and number of clusters, which works very well for 3D image processing. This substantially improved our speed, making our model surprisingly fast at calculating new paths to explore.

Updating the Cost Map with Predator Information

As mentioned earlier, we abstracted away the predator dynamics by replacing the predators with AR tags. One of the conventional approaches in literature to model predators are bounding boxes, which can work well for stationary predators but don't accurately capture the danger from predators scanning their environment. Moreover, our design constraint of unknown predator dynamics prevents us from using a game theory approach to solve the problem. Our unique approach is incorporating the predator's field of view into the path planning cost map, which in biological systems is information that's often quite easy to determine for unknown animals just from observation alone. By merging this with the predator's position and orientation from the AR tag locationing, we can augment our SLAM cost map with the danger of the predator's field of view.

To model the predator's field of view, we used the conventional "binocular vision" model shown below. This model splits our vision into two regions: "binocular vision" where we can use both eyes to see and "monocular vision" where we can only see things with one eye. We used a human's vision angle for our cost map (114 degrees total view angle, with the outside 40 degrees experiencing monocular vision).

Implementation of Navigation

Rather than decide navigation plans dynamically throughgame theory or machine learning, our goal is to explore overall trends in predator avoidance given a lack of proper defense mechanisms. A common method under these constraints is wall hugging, i.e. staying away from open spaces and moving close to walls or obstacles (think of all the cockroaches and spiders you found near the walls of your house). This gives the advantage of restricting predator’s field of view and can, once the prey is discovered, allow the prey to path plan an escape solution while the predator is still figuring out its obstacle avoidance. In the following sections, we investigate multiple mechanisms of wall hugging, from cost maps to path planning.

Path Planning

We used the ROS package rrt_exploration as the basis for our path planning, with several modifications to include the computer vision filters described above to improve speed. For our application, however, we modified RRT exploration’s metric for the information gain of frontier points to include a detriment if frontier points were near predicted predator locations. Below is a visualization for what this looks like (to the left is a map from gmapping as described above, and to the right are the paths generated by rrt_exploration for navigating the map):

Obstacle Inflation

In order to account for the realistic dimension of our robot, we need to modify the radius of obstacles in our cost map. We modified our cost values in the following equation:

where r_inscribed is the inscribed radius of the prey robot's shape, and γ is a parameter determining the exponential degradation of the cost function. The original implementation of gmapping uses an exponential degradation γ= 5, which caused the robot to move closer to the center of pathways when inside narrow corridors. We found that doubling this to γ = 10 substantially improved how well we could follow walls closely, especially in cluttered environments. We also decreased the freespace radius from 5 to 3. These changes also sped up our path planning in these cluttered environments while still keeping a safety measure in case of noise.

We can see the effect of these changes clearly in the below two videos. The left video is with the original parameters, where you can see the robot simply moving in the center of the pathway when trying to approach its target position. The right video is with our modified parameters, where you can see the robot wall hugging much better. You can even see the robot moving from obstacle to obstacle, which shows the application of the above cost map strategies can be scaled even to cramped environments.

Original Obstacle Expansion - Moves Near the Center

Our Modified Obstacle Expansion - Wall Hugging

Intra-Swarm Communication

In nature, animals like deer and monkey will warn others in the herd if they spot predators near by. These warning can greatly improve a herd’s survivability because the herd will not panic if the predators charge in from one animal's blind spot. In the scope of our work, we designed a communication system that allows prey robots to react to an incoming prey. To do this, we used a ROS package called multimaster-fkie. multimaster-fkie allows each robot to be their own ROS master, while still having the ability to share topics to other master. All of the communication in a multimaster network is also synchronized.

Results

Below, we've included two videos. The first is on an actual robot in the lab, and the second is a simulation.

With the real-life robot, we can see clear avoidance of the predator and its field of view, although the slowness of ar_track_alvar and the time it takes the cost map to update to dynamic updates is clearly deficient compared to our idealized calculations above. If you follow the cost map on the left part of the screen, you can see it updating to match the AR tag's position and orientation as the predator's "field of view" changes.

With the simulation, the predator is meant to be in the top left corner looking downwards (we weren't able to figure out how to insert extra URDF files in the Gazebo simulator for the predator). As you can see, the prey robot explores pretty much the entire bottom half of the map, moving away from the predator and moving along the walls once it sees the predator. Even when it explores the bottom half of the house and moves towards the top, it stops because it can't move forward without getting spotted.

Real Robot Demo

Simulation Demo

Conclusion

As we set out to do, we successfully managed to implement a predator avoidance algorithm for swarm applications. We explored a variety of approaches at multiple levels of the pipeline, from computer vision to post-processing to path planning, and we found that good predator avoidance is fundamentally a whole-stack system design rather than the job of one specific field.

We provide video evidence above both for real robots and in simulation that our prey robots properly avoid predator robots’ field of view. The prey robots were also able to execute conventional biological approaches to predator avoidance such as wall following to avoid detection.

We anticipate these findings may be helpful for surveillance and navigation. For example, in the military ground robots are among the heart and soul of discreet surveillance for their quietness, robustness, and versatility compared to alternative vehicles like drones. Applications like this on avoiding unknown enemies in an actively hostile environment could be extremely useful in extreme settings like these, where detection is on par with death.

At the same time, we also enjoyed exploring a fun side of robotics and looking at all the biological adaptations animals have out there to stay alive! There's a surprising amount of math in survival, and breaking down the first layer of it is one of the most exciting applications of robotics there can be.

The Real Predators

Ahad Rauf - EECS '20

Weiyu He - MechE Master's '21

Irving Fang - Data Science and Pure Math '20

Acknowledgments

The authors would like to thank Professor Ruzena Bajscy and the class GSI’s Valmik Prabhu and Christopher Correa for their wonderful input and feedback.

Google Sites

Report abuse