- Manoj Kumar Joshi (Email:- [email protected])
- Ashok Barthwal (Email:- [email protected])
- Yogesh Kumar (Email:- [email protected])
Earth observation data is crucial in natural/disaster response and other accidental stranded people cases in national parks and mountains. In case of a natural disaster large number of resources are needed to provide timely help to the victims. A co-ordinated effort between global or local disaster response team and volunteers makes a key difference. Latest observation data from satellites plays a key role. Although many Search and Rescue organizations are already utilizing satellite data in different ways (Mostly GIS), we think we can take this to next level. With availability of scalable graph like TigerGraph, it is possible to store earth observation data in terms of Vertices and Relationships which leads to faster availability of insights out of this data specially terrain traversal applications for rescue teams and volunteers.
- Natural disasters all around the world in the year 2008 to 2020 caused around 10 Millions injured and around 40 Millions displaced.
- Rescue team and volunteers need to be empowered with terrain insights they can use.
- GIS can lay out infographics and elevation maps in various interesting ways.
- Does not provide a quarriable interface to shortest path.
- By design meant to help the analyst and not the rescue worker or volunteer.
- Bring earth observation data into TigerGraph
- Equip TigerGraph with required UDF to process geo-spatial data.
- Create query interfaces to this data to generate insights like terrain traversal applications.
Earth observation/geography data is available from Satellite and OpenStreetMap (OSM). We attempt to solve difficult terrain problems by combining Satellite/OSM data and TigerGraph. With the combination of Tiger Graph and Geo-Spatial we can visualize geo-spatial use cases with respect to graph.
- We created UDF functions with the help of C bindings of uber H3. This allow us to call geo-spatial functions while traversing TigerGraph.
- We then did some pre-processing for our sample of satellite data. Which is elevation and multi spectral images gathered from USGS and Sentinel 2. In this pre-processing we aggregated Earth observation attributes at resolution 10,11 and 12 respectively and populated graph with it.
- We then created and optimized our queries related to traversal based on surface elevation, smoothness and distance. We kept vegetation as an extra attribute.
- After that we created front end graphical interfaces to utilize these queries.
-
Impactfulness:
- Natural disasters all around the world in the year 2008 to 2020 caused around 10 Millions injured and around 40 Millions displaced. For details click here Global and local search and rescue missions are launched every year around the world for stranded people as a result of natural disasters or otherwise. In the USA alone between 1992 and 2007 a total of 65,439 "Search and Rescue" (SAR) missions were conducted in National Parks. For reference See
- Adoption of GIS technologies for terrain awareness results more saved lives already (ref:https://www.researchgate.net/publication/326011470_Position_Tracking_and_GIS_in_Search_and_Rescue_Operations), We think our solutions can make more impact because they have an ability to take terrain insights directly to people on the ground.
- In the areas of Road/Natural Gas/Fresh water pipeline planning also our solution will be of direct help (ref:https://scholarworks.sjsu.edu/cgi/viewcontent.cgi?referer=https://www.google.com/&httpsredir=1&article=8173&context=etd_theses)
- As per Oil and Gas journal USA cost of pipelines vary from 3 to 5 Million USD per Kilometers (Ref:https://www.gem.wiki/Oil_and_Gas_Pipeline_Construction_Costs). Smart and efficient route planning based on terrain features can help to save millions of dollars.
-
Innovativeness:
- Path traversal solution based out of Earth observation data is unique (to best of our knowledge and experience).This has not been attempted because
- Satellite image processing is complicated and methods are still evolving.
- The kind of data structure needed to build on-demand insight applications were also evolving (Till Graphs became scalable databases)
- Existing technologies mostly utilize Digital Elevation and other earth observation data to create maps and info graphs ref. Because of the challenges of processing huge amount of data and lack of faster relations based search prevent other technologies to create land traversal solutions using earth observation data.
- Despite Tigergraph being a high performance graph DB, we faced performance challenges which we solved in an innovative ways. Our dataset has 607,624 vertices and 3,624,018 edges for smallest Resolution 12. Running traditional search algorithms were very slow. We also had to keep track of Maximum smoothness, Minimum Distance and Minimum elevation.
- We solved these challenges by using a variation of A-Start algorithm along with some control functions to control directions of search. We also developed a multi resolution search method to dramatically reduce number of vertices to be searched. This video (https://www.youtube.com/watch?v=n5YB-a0M7GU) discusses challenges and how we solved them.
- Path traversal solution based out of Earth observation data is unique (to best of our knowledge and experience).This has not been attempted because
-
Ambitious and complex graph:
- We ingested data from a relatively small area Santa Rosa Island, USA. This island is only 215 Square Km. When we created H3 resolution 10,11 and 12 vertices it constituted 708,882 Vertices (with 5 attributes) and 4,220,226 Edges.
- Although our sample data size is relatively small, It is highly scalable...
- Tigergraph as a database is scalable in itself.
- The algorithms we developed reduce the vertices to be considered for search and restrict search to an elliptical area using a control function. This way our solution is scalable to very large areas as well as it wont matter if number of vertices are increased.
- We implemented 3 Path traversal algorithms (one for each resolution) , 1 recursive algorithm for performance and 1 Shortest path to openstreetmap road. A typical 5 km long trail smoothest path search needs 274 hops to reach destination (which it does in 1 or 2 seconds).
- Algorithms including in this solution are capable of making path decisions from 10 meter wide Road but can be easily enhanced to make decisions on .5 meter trail as well.
-
Applicable graph solution
-
With the availability of satellite images via APIs (ref it is easy to launch this system to deliver path traversal based out of latest available data.
-
Apart from search and rescue organizations and volunteers our solution will also be very useful in "Road planning", "Natural Gas and water pipelines" For reference plz visit following links ..
- https://scholarworks.sjsu.edu/cgi/viewcontent.cgi?referer=https://www.google.com/&httpsredir=1&article=8173&context=etd_theses
- https://www.researchgate.net/publication/263058158_GIS-Based_Route_Planning_in_Landslide-Prone_Areas
- https://proceedings.esri.com/library/userconf/proc10/uc/papers/pap_1392.pdf
-
Other additions:
- Data: The Rasters images (image1,image2) of the Santa Rosa island are taken from sentinel satellite open source image for different bands(red band and near infrared band) with some elevation related information etc. After processing the resulting data will contain the csv (res_10_nodes, res_11_nodes, res_12_nodes, res_10_edges, res_12_edges, res_12_edges ) containing hex_id against every point and its elevation etc with grouping.
- Technology Stack:
- In data preparation we have used python as programming language.
- In UDF Functions we used C/C++ library h3 and used C/C++ as programming language.
- In Backend API we have used Node.js as programming language.
- In User Interface we have used HTML5, jquery as programming language.
- Video:
- Demo
- Docker
- Tigergraph(version : 3.5.0)
- Python In Docker Container (version > 3.0)
- Node.js and npm package manager
- apache or nginx
In the project we have three sub-modules. In order to replicate the project you only need to follow "Tigergraph schema and UDF function installations" and "User interface and API'S to communicate with UI". Tigergraph solution export files already contain the data required.
- 1- Tigergraph schema and UDF function installations.
- 2- User interface and API'S to communicate with UI.
- 3- Optional Data preparation (Please explore only to see how we pre-processed the data).
For demo purpose we have only processed and implemented data of Santa Rosa Island of California.
Since our objective is to empower volunteers at the time of crisis, we want to take this prototype to a minimum viable product level and explore its practical usage with various organizations. We also plan to integrate more features to the applications and graph and work with Open data Cube project to gather near real time satellite imagery and other kind of data.
- Build regular pipeline from Satellite data to TigerGraph
- Integrate data pipeline directly with open data cubes like “DIGITAL EARTH AFRICA” and “DIGITAL EARTH AUSTRALIA” to have a near real time update of Earth observation data into tigergraph.
- Expand applications for Rescue teams and Volunteers
- Develop more algorithms and include attributes like “FLOOD Data”, “ELECTRICITY STATUS” and provide more real time series information. Develop Mobile applications which can interact with Tigergraph along with other
- Collaborate with organizations like disastercharter.org
- Collaborate with various organizations who are helping co-ordinated Search and rescue and facilitate them with our solution.
