A Versatile Approach for Adaptive Grid Map** and Grid Flex-Graph Exploration with a Field-Programmable Gate Array-Based Robot Using Hardware Schemes
Abstract
:1. Introduction
- Hardware-based behavior using quad-grid construction was developed for the exploration algorithm.
- Distance-based frontier detection and local-occupancy-based frontier detection graph algorithms with probabilistic map** were developed with PR flow and hardware schemes.
- Redundancy checks were developed for the complete exploration module of the environment to optimize local map data and dynamic graphs using hardware schemes.
- A hardware-driven partial reconfiguration process was incorporated to execute multiple algorithms based on event-driven conditions.
2. Hardware-Based Algorithms
2.1. Algorithm for Exploring Grid Flex Graphs Using Hardware-Based Methods
2.1.1. Exploring Grid-Based Graph Using a Hardware-Based Algorithm
Algorithm 1. Pseudocode for grid construction and graph exploration. |
1. Initialize RS = {SF, SL, SR, SB}, SD = {SFR, SFL, SLB, SRB}, RP = {xi, yi, θi}, E = {M × N}, RD, GD 2. Initialize F = {7{R × C}}, digital compass direction 3. Case_1 (Grid_Construction) 4. State1_1: if ((RS == dmax) && (SD == ddmax))?((RS == dmin) && (SD == ddmin))? State3_1@Update_map: State2_1@Graph_Exploration: State1_2; 5. State1_2: if ({SF, SR} > dmax)? State_forward: State1_3; 6. State_forward: if (GD, RD == dmax)? (RD == 90°): R@Fwd: R@Left: R@Right; 7. State1_3: State3_4@Update_map, repeat State_1 8. end case 9. Case_2 (Graph_Exploration) 10. State2_1: if ((node_queue () == 0)? ((RS == Dmax) && (SD == DDmax))? State1_1@Grid_Construction: State4_1@complete_exploration: State2_2; 11. State2_2: for (int i = 0; I ≤ n − 1; i++) { If (RS, SD [i] ≤ Dmax) C_child_nodes[i] = C[i]; } 12. State2_3: if (((C1 == C2) ≤ Dmax) && (C4 == Dmax)) Robot Follow around the direction @turn_right, Odometer ++ else if (((C1 == C4) ≤ Dmax) && (C1 == Dmax)) Robot Follow along the direction 13. State2_4: if ((C1 == C2) ≥ Dmax) && (C4≤ Ddmax)?(Time == 10)?1′b1: State2_4@Graph_Exploration: State2_5; 14. State2_5: State3_2@Update_map, Repeat State2_1 15. end case |
Algorithm 2. Pseudocode for updating map and complete exploration. |
|
2.1.2. Performance Metrics for the Proposed Method
2.2. Hardware Schemes for the Grid Flex-Graph Exploration Approach
3. Results
Author Contributions
Funding
Institutional Review Board Statement
Informed Consent Statement
Data Availability Statement
Acknowledgments
Conflicts of Interest
References
- Available online: https://www.statista.com/outlook/tmo/robotics/worldwide#:~:text=The%20Robotics%20market%2C%20worldwide%2C%20is,bn%20in%20the%20same%20year (accessed on 19 November 2023).
- Lluvia, I.; Lazkano, E.; Ansuategi, A. Active Map** and Robot Exploration: A Survey. Sensors 2021, 21, 2445. [Google Scholar] [CrossRef] [PubMed]
- Obwald, S.; Bennewitz, M.; Burgard, W.; Stachniss, C. Speeding-Up Robot Exploration by Exploiting Background Information. IEEE Robot. Autom. Lett. 2016, 1, 716–723. [Google Scholar] [CrossRef]
- Mu, B.; Giamou, M.; Paull, L.; Agha-Mohammadi, A.-A.; Leonard, J.; How, J. Information-based Active SLAM via topological feature graphs. In Proceedings of the 2016 IEEE 55th Conference on Decision and Control (CDC), Las Vegas, NV, USA, 12–14 December 2016; pp. 5583–5590. [Google Scholar] [CrossRef]
- Liu, S.; Li, S.; Pang, L.; Hu, J.; Chen, H.; Zhang, X. Autonomous Exploration and Map Construction of a Mobile Robot Based on the TGHM Algorithm. Sensors 2020, 20, 490. [Google Scholar] [CrossRef] [PubMed]
- Wattanavekin, T.; Ogata, T.; Hara, T.; Ota, J. Mobile Robot Exploration by Using Environmental Boundary Information. ISRN Robot. 2013, 2013, 954610. [Google Scholar] [CrossRef]
- Gonzalez-Arjona, D.; Sanchez, A.; López-Colino, F.; De Castro, A.; Garrido, J. Simplified Occupancy Grid Indoor Map** Optimized for Low-Cost Robots. ISPRS Int. J. Geo-Inf. 2013, 2, 959–977. [Google Scholar] [CrossRef]
- Gao, H.; Zhang, X.; Wen, J.; Yuan, J.; Fang, Y. Autonomous Indoor Exploration Via Polygon Map Construction and Graph-Based SLAM Using Directional Endpoint Features. IEEE Trans. Autom. Sci. Eng. 2019, 16, 1531–1542. [Google Scholar] [CrossRef]
- Wang, H.; Jenkin, M.; Dymond, P. Enhancing Exploration in Topological Worlds with a Directional Immovable Marker. In Proceedings of the 2013 International Conference on Computer and Robot Vision, Regina, SK, Canada, 28–31 May 2013; pp. 348–355. [Google Scholar] [CrossRef]
- Wirth, S.; Pellenz, J. Exploration Transform: A stable exploring algorithm for robots in rescue environments. In Proceedings of the 2007 IEEE International Workshop on Safety, Security and Rescue Robotics, Rome, Italy, 27–29 September 2007; pp. 1–5. [Google Scholar] [CrossRef]
- Yu, N.; Wang, S. Enhanced Autonomous Exploration and Map** of an Unknown Environment with the Fusion of Dual RGB-D Sensors. Engineering 2019, 5, 164–172. [Google Scholar] [CrossRef]
- Argenziano, F.; Suriani, V.; Nardi, D. Enhancing Graph Representation of the Environment through Local and Cloud Computation. ar** and Navigation with Self-Organizing Neural Networks. IEEE Trans. Neural Networks Learn. Syst. 2022, 33, 7101–7113. [Google Scholar] [CrossRef]
- Petavratzis, E.; Moysis, L.; Volos, C.; Nistazakis, H.; Mu?Oz-Pacheco, J.M.; Stouboulos, I. Chaotic Path Planning for Grid Coverage Using a Modified Logistic-May Map. J. Autom. Mob. Robot. Intell. Syst. 2019, 14, 3–9. [Google Scholar] [CrossRef]
- Kvitko, D.; Rybin, V.; Bayazitov, O.; Karimov, A.; Karimov, T.; Butusov, D. Chaotic Path-Planning Algorithm Based on Courbage–Nekorkin Artificial Neuron Model. Mathematics 2024, 12, 892. [Google Scholar] [CrossRef]
- Wan, Z.; Yu, B.; Li, T.Y.; Tang, J.; Zhu, Y.; Wang, Y.; Raychowdhury, A.; Liu, S. A Survey of FPGA-Based Robotic Computing. IEEE Circuits Syst. Mag. 2022, 21, 48–74. [Google Scholar] [CrossRef]
- Vipin, K.; Fahmy, S.A. ZyCAP: Efficient Partial Reconfiguration Management on the **linx Zynq. IEEE Embed. Syst. Lett. 2014, 6, 41–44. [Google Scholar] [CrossRef]
- Tadigotla, V.; Sliger, L.; Commuri, S. FPGA implementation of dynamic run-time behavior reconfiguration in robots. In Proceedings of the 2006 IEEE Conference on Computer Aided Control System Design, 2006 IEEE International Conference on Control Applications, 2006 IEEE International Symposium on Intelligent Control, Munich, Germany, 4–6 October 2006; pp. 1220–1225. [Google Scholar] [CrossRef]
Symbol | Symbol Description |
---|---|
RS | Robot sensors facing 90° angles {SF, SL, SR, SB}. F: front, L: left, R: right side, B: backward. |
SD | Robot sensors facing angles 45° from each RS {SFR, SFL, SBL, SBR}. FR: front-right, FL: front-left, LB: backward-left, RB: backward-right. |
RP, F | Robot position (xi, yi, θi) and memory required to store the data {7{R × C}}. |
E | Unknown environment is represented in a 2D space with a boundary limit of M × N. There are objects whose positions are not known. |
Dmax DDmax | Maximum distance in robot’s vicinity. Maximum diagonal distance in robot’s vicinity. |
dmax ddmax | Maximum distance in grid’s vicinity. Maximum diagonal distance in grid’s vicinity. |
dmin ddmin | Minimum distance in grid’s vicinity. Minimum diagonal distance in grid’s vicinity. |
Mij | The occupancy state of cell (i, j) in the grid. Mij = 1 indicates the presence of an object, and Mij = 0 indicates a free space. This binary matrix represents the occupancy map. |
Gij | The graph representation of the grid. Gij = 1 indicates a connection between nodes (i1, j1) and (i2, j2), and Gij = 0 indicates no connection. This graph dynamically evolves based on sensor readings and completion detection. |
Di | Ultrasonic distance readings from the eight sensors. These variables provide information about the distances in the robot’s vicinity between the node and surrounding neighboring nodes. |
FDmax, FD, FG, FV, FO, FMH, PMH | Final maximum distance, final direction, final grid, final vertex, final object, final map history, and previous map history, respectively. |
Q, m × n | Number of grid cells and the size of the grid represented as a quad-grid. |
Et | Exploration completion at time step t (a value between 0 and 1, where 1 represents no exploration and 0 represents complete exploration). |
Module | LUT | BRAM | DSP Slice |
---|---|---|---|
Communicating modules (sensors, motors, UART, and **linx IP cores) | 6552 | 20 | 38 |
Control unit and PWDC sensor fusion | 4686 | 18 | 32 |
Complete exploration module | 5586 | 32 | 36 |
PR in environment with dynamic objects | 6358 | 16 | 16 |
PR in environment with static and dynamic objects | 7525 | 22 | 34 |
Total | 30,707 | 108 | 156 |
Reference No. | Methods Used | Computing Device | FF | Four-Input LUT | DSPs | Internal RAM | External RAM | Reconfigurable Feature |
---|---|---|---|---|---|---|---|---|
[7] | Backtracking occupancy grid-based map** | FPGA **linx Spartan3-1000 (**linx, Hyderabad, India) | 3228 | 4581 | 18 | 32 | 512 | No |
[24] | Scan-matching genetic SLAM | **linx Virtex-5 (**linx, Hyderabad, India) | 2377 | 4573 | 9 | 131 | Not used | No |
Proposed approach | Grid flex-graph exploration | **linx Zed board FPGA (**linx, Hyderabad, India) | 4686 | 6358, 7525 | 16, 34 | 16, 22 | Not used | Yes |
Reference Papers | Sensory Approach | Algorithm | Hardware | Pros | Cons | |
---|---|---|---|---|---|---|
Method | Fusion | |||||
[3] | Sensor data | X | Frontier-based graph approach | CPU | Rapidly encompasses the area with its sensors beyond the capabilities of a greedy exploration system. | Need to provide additional information before exploration. |
[4] | Laser scans | X | Topological feature graph | CPU | Vertices and edges can be learned using the depth of the image or laser scans. | Limited to traversing the edges of graphs. |
[9] | Sensor perception data | X | Single immovable directional marker | CPU | Loop-closing problem in embedded topological worlds using an external marking aid. | Selection of an optimal location for the marker is not defined, the computational cost is high, and this method is limited to simulation. |
[14] | Sensor data | X | Predictive exploration approach | CPU | The structures of environments in unexplored areas are obtained using previous data. | Utilizing prior knowledge while performing autonomous operation. |
[16] | 2D laser range finder | X | Safe and Reachable Frontier Detection (SRFD) | CPU | Data structure for efficient frontier extraction and management. | Need for large computational analysis and power consumption. |
Proposed approach | Ultrasonic sensor data | √ | Grid flex-graph exploration in static and dynamic environments | FPGA | Grid construction and graph exploration are novel approaches to compute loop closure and VLSI architectures. | Optimization of data handling for different sensors to compute loop closure for multi-robotic systems will be integrated in the near future. |
Map-Type | Ultrasonic Sensor Data Fusion | Sensor Data Fusion Positive Rate | Error Rate |
---|---|---|---|
Topology–grid hybrid map/occupancy grid map | Environment with static and dynamic objects | 97.2% | 2.4% |
PR in environment with dynamic Objects | 98.8% | 1.6% | |
PR in environment with static and dynamic objects | 99.4% | 0.8% | |
Topo-metric graph/graph-based representation | Environment with static and dynamic objects | 96.2% | 3.6% |
PR in environment with dynamic Objects | 97.2% | 2.2% | |
PR in environment with static and dynamic objects | 98.6% | 1.6% |
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. |
© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Basha, M.; Siva Kumar, M.; Chinnaiah, M.C.; Lam, S.-K.; Srikanthan, T.; Divya Vani, G.; Janardhan, N.; Hari Krishna, D.; Dubey, S. A Versatile Approach for Adaptive Grid Map** and Grid Flex-Graph Exploration with a Field-Programmable Gate Array-Based Robot Using Hardware Schemes. Sensors 2024, 24, 2775. https://doi.org/10.3390/s24092775
Basha M, Siva Kumar M, Chinnaiah MC, Lam S-K, Srikanthan T, Divya Vani G, Janardhan N, Hari Krishna D, Dubey S. A Versatile Approach for Adaptive Grid Map** and Grid Flex-Graph Exploration with a Field-Programmable Gate Array-Based Robot Using Hardware Schemes. Sensors. 2024; 24(9):2775. https://doi.org/10.3390/s24092775
Chicago/Turabian StyleBasha, Mudasar, Munuswamy Siva Kumar, Mangali Chinna Chinnaiah, Siew-Kei Lam, Thambipillai Srikanthan, Gaddam Divya Vani, Narambhatla Janardhan, Dodde Hari Krishna, and Sanjay Dubey. 2024. "A Versatile Approach for Adaptive Grid Map** and Grid Flex-Graph Exploration with a Field-Programmable Gate Array-Based Robot Using Hardware Schemes" Sensors 24, no. 9: 2775. https://doi.org/10.3390/s24092775