PRE2019 3 Group9

Group members

Name	Study	Student Number
Nick Reniers	Technische Wiskunde	1258362
Jankatiri Boon	Werktuigbouwkunde	1003254
Milan Hutten	Software Science	0997241
Mendel van der Vleuten	Technische Wiskunde
Ferenc Sterkens	Werktuigbouwkunde

Problem statement

Animal researchers are unable to effectively gather data of subterranean species without destroying their burrows or tunnel systems.

Users

Researchers of subterranean animals or underground tunnel systems

User Needs

The following list of user needs does not focus on any particular type of researcher or animal species yet and thus requires modification

• Observe animals within their burrows
• Visualize burrows
• Keep track of population growth
• Safely (both for the researcher and the animal) extract animal from their burrow

Animal Needs

The following list of user needs does not focus on any particular animal species yet and thus requires modification

• Be disturbed as little as possible (May require more elaborate description)

Biological study fields

This list is composed purely based on the short descriptions of the studies.

• Ethology: the study of the behaviour of animals. Requires ability to observe individuals.
• Entomolgy, Herpetology, Ichtyology, Mammalogy and Ornithology: the studies of insects, reptiles and amphibians, fish, mammals and birds respectively. Purely based on the species we focus on.
• Biogeograph: the study of the distribution of species spatially and temporally. Requires ability to observe individuals and count populations.
• Biomechanics: the study of the mechanics of living beings. Requires ability to observe individuals. Specifically interesting for mechanics that do not or rarely occur above ground.
• Chronobiology: the study of periodic events in living systems. Requires ability to observe individuals
• Conservation biology: the study of the preservation, protection, or restoration of the natural environment, natural ecosystems, vegetation, and wildlife. Requires ability to count populations.
• Ecology: the study of the interactions of living organisms with one another and with the non-living elements of their environment. Requires ability to observe individuals.
• Sociobiology: the study of social behavior in terms of evolution. Requires ability to observe individuals.

Requirements

The robot should be able to:

• Safely and autonomously navigate the specified underground systems
• Map these systems adequately
• Be able to return to the user after completing its tasks

Approach

We approach the problem in a very practical manner, we opt to create a robot that autonomously investigates underground tunnels and maps them. We first make a selection of subterranean animals for which we can map their corresponding burrows, and then research details of these animals and underground systems as to prepare a robot that can safely navigate them

Objectives and milestones

• Make a selection of animals for which it is feasible to construct a robot that navigates their burrows
• Research the animals specified in the first milestone and their corresponding underground systems
• Make a construction plan for a robot that could navigate said tunnels adequately
• Prepare software for path finding in burrowss
• Prepare software for mapping the underground systems
• Construct the robot
• Validate the workings of the robot and summarize our findings

State-of-the-art

A robotics-oriented taxonomy of how ethologists characterize the traversability of animal environments surveys 21 studies of how ethologists characterize the environments through which animals traverse and groups the found characteristics into three broad catergories: local navigational constraints, surface properties, and global layout properties. From these the article makes four recommendations to aid roboticists in selecting a suitable robot for particular environments, building testbeds for the testing and comparing of robots and the collection of data about an environment.

Burrowing rescue robot referring to a mole's shoveling motion proposes an novel inspecting robot designed to inspect survivors at landslide disaster sites. Its proposed propulsion method is inspired by the shoveling motion of a mole.

Deformable Octahedron Burrowing Robot explores the use of a deformable octahedron robot for the autonomous exploration of complex confined spaces. Unlike most other robots, it is able to adapt its shape to better traverse intricate sections of cavities.

Soft Robotic Burrowing Device with Tip-Extension and Granular Fluidization proposes a soft robotic device that burrows through dry sand, leveraging the principles of both tip-extension and granular fluidization.

A Remote Operated Multi-Tracked Vehicle for Subterranean Exploration of Gopher Tortoise Burrows discusses a topic closely related to the one discussed on this page. This article describes a remotely operated vehicle designed to survey and investigate gopher turtoise burrows for the estimation of populations.

CRABOT: A Biomimetic Burrowing Robot Designed for Underground Chemical Source Location describes a prototype burrowing robot called CRABOT developed to help find leaks in undergroud piplines transporting chemicals.

Cockroaches traverse crevices, crawl rapidly in confined spaces, and inspire a soft, legged robot explains how cockroaches way of traversing small crevices support a model of a new unexplored mode of locomotion "body-friction legged crawling" which could be applied in robotics.

Towards a Mobile Mapping Robot for Underground Mines describes a robot platform which can help construct 3D environment underground mappings.

Development of Search-and-rescue Robots for Underground Coal Mine Applications describes the design and development of a coal mine rescue robot which can be used as a reference.

Autonomous Robotic Monitoring of Underground Cable Systems investigates the possibility of autonomous robotic mobile platforms for monitoring infrastructures

PATH FINDING - Dijkstra’s and A* Algorithm’s summarizes and elaborates on famous path finding algorithms

A shortest-path algorithm for solving the fleet management problem in underground mines uses a shortest path algorithm to manage and schedule underground infrastructure

A Robotic System for Underground Coal Mining "describes a system that automates a continuous miner, enabling it to maneuver in highly constrained environments..."

An underground explorer robot based on peristaltic crawling of earthworms takes inspiration from the earthworm to develop a robot that uses peristaltic crawling which is useful for underground exploration

Evolving Sparse Direction Maps for Maze Pathfinding This paper focuses on evolving data that allows an entity to reach a point quickly from any other point in the maze. This kind of map is generated by a simple genetic algorithm. But this method did not necessarily give the shortest path.

View-Based Cognitive Mapping and Path Planning A view graph is created where views are seen as nodes and the movement between views are seen as edges. This graph retains the topological and directional structure of the maze. A neural network can learn the view graph during a random exploration which then allows it to generate expectations about which views will be encountered next.

Design and Implementation of a Path Finding Robot Using Flood Fill Algorithm This article tries to find out how effective the flood fill algorithm is for maze solving. This algorithm was implemented in a small robot with ultrasonic range sensor and wheel rotation decoders. The robot was able to map the maze and afterwards would do a second run where it tried to find a shortest route to the goal.

Portal-Based True-Distance Heuristics for Path Finding This article introduces a new true distance memory based heuristics as a way to obtain admissible heuristics for explicit stat spaces.

Micromouse : Maze solving algorithm This article is about the creation of a small scale robot which navigates a maze based on sensors, the algorithm used was based on the bellman flooding algorithm with a maze consisting of 16x16 cells.

Path finding simulator for mobile robot navigation This paper is focused on creating a path finding simulator for pioneer 3dx mobile robot. The simulator is provided with multiple algorithms, it can then use any or multiple them (with comparison) to find the shortest possible route.

Solving a Reconfigurable Maze using Hybrid Wall Follower Algorithm This paper expands on the wall follower method of solving a maze, the new algorithm combines left and right hand rules and tests them on several mazes. This hybrid algorithm improved the maze solving abilities significantly compared to just following the wall.

G. Kouros, I. Kostavelis, E. Skartados, D. Giakoumis, A. Simi, G. Manacorda, D. Tzovaras, 3D Underground Mapping with a Mobile Robot and a GPR Antenna, 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2018), Madrid, Spain, October 2018 This paper focuses on scanning subsurface environments using a GPR antenna. This information is then used to create a 3D model of the system.

Kevin James Worrall, David Firstbrook, Thaleia Flessa, Euan McGookin, Douglas Thomson, Patrick Harkness, “Modelling and Control of a Biologically Inspired Trenchless Drilling Device”, in The 12th International UKACC Conference on Control, Sheffield, UK, 5-7 Sept 2018 This work presents the methods used and initial findings of the control of the model for an autonomous trenchless drilling device, with bioinspired worm-like locomotion. The model is validated using Inverse Simulation. The initial control is detailed with data from the simulation and experimental device.

G. Kouros, C. Psarras, I. Kostavelis, D. Giakoumis, D. Tzovaras, Surface/Subsurface Mapping with an Integrated Rover-GPR System, A Simulation Approach, IEEE International Conference on Simulation, Modeling and Programming for Autonomous Robots (SIMPAR 2018), Brisbane, Australia, May 2018. This paper further focuses on the GPR antenna robot, only this time it has an intregrated antenna which allows it to seamlessly integrated to build adjunct surface and subsurface maps.

A. Simi, D. Pasculli, G. Manacorda, “Badger project: GPR system design on board on a underground drilling robot”, 10th International Workshop on Advanced Ground Penetrating Radar (IWAGPR 2019), Hague, The Netherlands, Sep 2019 The present paper presents some results of EU founded project called Badger, the first underground robotic system that can drill, maneuver, localize, map and navigate in the underground space, and which will be equipped with tools for constructing complex geometry networks of stable boreholes.

Effort Table

Week 1

Name	Total	Break-down
Nick Reniers	7 hours	Introduction lecture (2h), Meeting discussing subject (2h), Studying papers and editing wiki(3h)
Jankatiri Boon	6 hours	Introduction lecture (2h), Meeting discussing subject (2h), Studied papers and editing wiki (2h)
Milan Hutten	7.5 hours	Introduction lecture (2h), Meeting discussing subject (2h), Studied papers (3.5h)
Mendel van der Vleuten	8 hours	introduction lecture (2h), small scale test code (2h), meeting discussed subject (1,5h), studying papers (2,5h)
Ferenc Sterkens

Week 2

Name	Total	Break-down
Nick Reniers
Jankatiri Boon
Milan Hutten	6.25 hours	Tutor meeting (20m), Group meeting (40m), Composing biological study list (30m), Looking for Interview Candidates (4.5h), Composing list of user needs and animal needs (15m)
Mendel van der Vleuten		Tutor meeting (20m), Group meeting (40m)
Ferenc Sterkens

Interview Candidates

prof.dr.ir F (Frank) van Langevelde has only 3 publications related to soil fauna. In these studies, they mainly refer with "soil fauna" to smaller critters such as nematodes, collembola (springtails) and other small arthropods inhabiting the soil. Most of which either do not create burrows but just tunnels through moving around in the soil. Their sampling of soil fauna can be oversimplified as extracting samples from the natural environment, extracting the desired type of animal from those samples, for example extracting collembola using tullgren funnels, and doing the required measurements. Because most species do not create burrows and because of the effectiveness of the current sampling strategy, the use of robots in this scenario does not seem to be a viable option.

• Van Langevelde, F., V. Comor, S. de Bie, H.H.T. Prins and M.P. Thakur (2020) Disturbance regulates the density – body mass relationship of soil fauna. Ecological Applications 30:e02019
• Thakur, M.P., M.P. Berg, N. Eisenhauer and F. van Langevelde (2014) Disturbance–diversity relationships for soil fauna are explained by faunal community biomass in a salt marsh. Soil Biology & Biochemistry 78:30–37
• Comor, V., M.P. Thakur, M.P. Berg, S. de Bie, H.H.T. Prins and F. van Langevelde (2014) Productivity affects the density – body mass relationship of soil fauna communities. Soil Biology & Biochemistry 72:203–211

dr.ir. AR (Anouschka) Hof has mostly done studies into the decline of the western hedgehogs pupulations in europe, and mainly in Great Britain, when it comes to soil fauna. This makes her an interesting candidate, though there are two things to consider. First, she seems to mostly get data via questionaires rather than field study. Just like with the sampling of the soil fauna done by Langevelde, the questionaire might be more effective then using robots. Secondly, a hedgehogs den is not very complex, and not even always underground, making pathfinding not a big priority. If a robot would be used, a remoted controlled one would probably easily suffice.

• The impact of grassy field margins on macro-invertebrate abundance in adjacent arable fields
• A study of the current status of the hedgehog (Erinaceus europaeus), and its decline in Great Britain since 1960
• The value of green-spaces in built-up areas for western hedgehogs
• Quantifying the long-term decline of the West European hedgehog in England by subsampling citizen-science datasets
• Factors affecting hedgehog presence on farmland as assessed by a questionnaire survey
• European terrestrial gastropod distribution. How may climate change affect their diversity and current distribution
• Investigating the role of the eurasian badger (Meles meles) in the nationwide distribution of the western european hedgehog (Erinaceus europaeus) in England
• Local variations in small scale movements of hedgehogs in rural areas.
• Egels in de problemen?

Y (Yorick) Liefting BSc is not a biological scientist himself, but he experiments with new technology and develops tools to support research.

Path finding

Given that we want to map underground tunnels of a specific species of subterranean animals, we need a systematic and preferably mathematically adequate way to represent different important aspects of the tunnels. The most straightforward way to do this is by the usage of the mathematical objects that are graphs. A graph G is a tuple G=(V,E) consisting of a vertex set V and an edge set E. Here, the edge set E contains unordered pairs of vertices between which an edge is present. There is also a variant of graphs in which the vertex pairs are ordered, but for the purpose of tunnel mapping, this is inconvenient. We can also consider the concept of a multigraph, in which multiple edges are possible between the same two vertices, this may be the case for some certain species of animals, but this demands further research. For now, we will assume simple undirected graphs as representatives for the tunnels of our species of animals.

For the purpose of mapping an underground tunnel system in general, one can deploy a multitude of graph algorithms. The most obvious algorithms for this purpose are depth first search and breadth first search, which greedily traverse a graph (representing the underground system of the animal). We can also look into finding specific points of interest depending on the animals we want to investigate. For example, one may be particularly interested in finding a nest in a mole underground system. For such purposes, specialized search algorithms that take into account the known properties of such points of interest, may be optimal.

Given that we have found the graph corresponding to the subterranean structure we want to investigate, we can look at some interesting properties of the graph. Examples would be the minimum spanning tree of the graph or the (non-)existence of cycles and connectedness.