















\section*{Acknowledgements}

This work was supported by the Academy of Finland's AutoSOS project with grant number 328755. This project has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 751615.

\bibliographystyle{IEEEtran}


\section{Introduction}


\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{fig_new/security_in_robotics_process_v5.pdf}
    \caption{Classification of data acquisition and analysis processes in autonomous robots and matching security layers.}
    \label{fig:concept}
\end{figure}

With robots and autonomous robots having an increasing penetration across multiple aspects of our society, more attention is being paid to the safety and security aspects in robotic operation~\cite{kirschgens2018robot}. The differentiation between safety and security often becomes fuzzy, with the safety term being utilized to refer to human-robot interaction~\cite{bragancca2019brief}, or to the safety of the robot itself~\cite{huang2014rosrv}. In either case, safe operation of an autonomous robot requires tight control over the security of the data being used, from data defining mission instructions to sensor data. Figure~\ref{fig:concept} shows a layered classification of stages in which information is either collected or processed by an autonomous robotic system. This figure extends the cyberattacks categorization in~\cite{clark2017cybersecurity}, and also takes into consideration that the internal processes can be modeled as a software-defined network from a more abstract point of view~\cite{akhunzada2015securing}. Many robotic frameworks, such as the Robot Operating System (ROS) fall into this consideration~\cite{rivera2019ros}. From the cybersecurity domain point of view, the acquired sensor data needs to be secured as well. This represents an additional challenge. Therefore, an essential aspect in the operation of autonomous robots is to be able to validate both data being shared among subsystems and external systems (a controller or other robots), but also data defining or characterizing the way the robot, seen as a cyber-physical system, interacts with its environment.


A relevant precedent in securing multi-robot cooperation was introduced by Castelló Ferrer et al. in~\cite{ferrer2019secure}, where the authors leveraged Merkle trees to cope with byzantine robots in cooperative missions within swarms of robots. The main novelty of their work is the introduction of a framework for validating data in robots without relying on the data itself, by encoding mission instructions in Merkle trees. Merkle trees are cryptographic structures that enable validation of data through cryptographic proofs that do not involve the data itself.

We aim at extending previous works into a more general framework focusing on encoding not only of mission instructions but also on the relationship between the possible ways in which a mission can be completed. In~\cite{ferrer2019secure}, one of the main research questions is whether it is possible to provide the ``blueprint'' of a robotic mission without describing the mission itself. In this paper, we delve into the possibilities and limitations of encoding instructions, exploring different application scenarios and developing more specific ways in which this idea can be integrated into real robotic missions.
Here, we go beyond separating data verification from the data itself, towards defining new implicit ways for defining complex robotic workflows. We first describe the framework and the different possibilities, from human-robot interaction to collaborative robots, and then provide a proof of concept with navigation instructions. This proof of concept demonstrates that traditional robot behavior can be maintained with minimal impact on robustness and applicability even when providing full mission codification, opening the door to more secure and safe deployment of autonomous robots.




Summarizing the previous considerations, we have found an unexplored research gap in robust data validation schemes for autonomous or semi-autonomous robots. The main research questions that we find so far unanswered extend the work in~\cite{ferrer2019secure} towards broader data validation in autonomous robots:

\begin{itemize}
    \item Is it possible for a robot to safely and securely interact with its environment, operators or other robots in a way that it has zero a priori knowledge of the mission itself;
    \item can encoded information revealing no explicit mission instructions maintain the level of efficiency and applicability of current robotic workflows; and, finally,
    \item can these encoded mission instructions be utilized to simultaneously validate their integrity but also the progress of the mission, together with local information such as sensor inputs and operation of actuators.
   
   
   
\end{itemize}

The first of the above questions applies to a wide variety of situations. For instance, whether a robot in a factory can be given assembly instructions that it cannot understand until the assembly process starts, or whether a robot can be given a map that it can only understand when it starts to navigate its environment. An even more interesting situation occurs when a robot can interact with a human or another robot in a predefined way only when a series of conditions are met. The latter two questions extend the same concept towards more concrete aspects: whether these encoded instructions can be adapted to current robotic algorithms and workflows, extending previous works relying on random movement, and, finally, whether instructions understood by the robots can, \textit{simultaneously}, validate that all processes are working properly. Thus, we are asking whether a single framework can define both end-to-end data validation and define encoded instructions that enable a robot to securely and safely interact with its environment.


These considerations cover the validation of a robot's operation from end to end: from validating sensor data and the correct operation of actuators to validating mission instructions and information received from an external controller. In our experiments, we consider a navigation or exploration mission where a priori information (features) about the environment is available to the mission controller or robot operator (operator hereinafter). In this scheme, an operator generates a set of encoded instructions by hashing the description of a set of landmarks (waypoints) in the environment. The set of encoded landmarks is then given for autonomous robots which utilize them to navigate the objective environment with zero a priori knowledge of it. The encoded landmarks are given to the robots in the form of a navigation graph which also includes information about how to navigate between consecutive landmarks. Because all information is encoded, we minimize the amount of raw data a priori exposed at the robots.



The main contributions of this work are

\begin{enumerate}
    \item the definition of an end-to-end validation framework for autonomous robots based on encoded instruction graphs;
    \item the introduction of a novel approach that encodes a navigation graph utilizing cryptographic hashes to encode environment features, and
    \item the definition of a set of methods that allow robots to follow encoded mission instructions while validating their sensor data without external feedback.
\end{enumerate}



The remainder of this paper is organized as follows. In Section~II, we overview previous works that address security issues in robotic systems. Section~III then introduces the proposed framework,
and describes different use cases
From Section~IV onward, we delve into a proof of concept
for robotic navigation. In that direction, Section~IV introduces the implementation details for an encoded navigation graph,
with Section~V presenting the methodology we have followed in our simulations and experiments. Section~VI describes the experimental results. Finally, Section~VII concludes the work and outlines future research directions.












\section{Background}

There has been a growing interest in securing robotic systems, partly owing to the increased connectivity with which robots are equipped. This is partly due to an increasing amount of data exchange modalities with new attack vectors in remote control commands~\cite{liu2005ibotguard}, telemetry~\cite{rodday2016exploring}, offloading computation~\cite{queralta2020enhancing, wan2016cloud}, robot-to-robot communication~\cite{ferrer2019secure, queralta2020blockchain}, and human-robot interaction~\cite{miller2018social}.

Multiple research efforts have been devoted to studying cybersecurity issues in robotics. In~\cite{clark2017cybersecurity}, Clark et al. review and discuss the main security threads to robotic systems, from spoofing sensor data to denial of service attacks, and including other typical vector attacks such as malicious code injection or signal interference. However, this analysis only takes into account the security aspect in robotics from the cybernetic point of view, without considering the physical dimensions in which robots operate. The interaction of a robot with its environment presents key issues that cannot be addressed with traditional risk mitigation techniques from the cybersecurity domain. An early work in this direction was presented by Py et al. in 2004~\cite{py2004dependable}, where the authors introduced an execution control framework for autonomous robots that would analyze the data obtained from the behavior of the robot through a \textit{state checker}. A more recent work taking into account the nature of robotic operations was presented by Tang et al.~\cite{tang2018event}, where sensor data was estimated through a denial of service attack. Similarly, in~\cite{tiku2019overcoming}, Tiku et al. introduced a methodology for overcoming security vulnerabilities in a deep learning localization method by introducing adversarial training samples.
All these approaches, however, take the point of view of data security in information systems and do not explicitly involve the cyber-physical nature of autonomous robots and their interaction with the environment, which is the objective of this paper. In terms of distributed and multi-robot systems, most efforts have been directed towards the analysis and mitigation of security issues from a networking perspective~\cite{rahman2019evaluation}.

From the point of view of data validation, Legashev et al. described an approach for monitoring, certification, and validation of the operation of autonomous robots~\cite{legashev201monitoring}. The authors' aim was to define a generic framework from a legislative approach, relying on periodic telemetry data obtained from autonomous robots and, in particular, autonomous vehicles. 
The framework focuses on validating the robot's operation but not the data itself. The only method available to validate the data itself in this work is through statistical analysis and detection of statistical abnormalities. Data integrity was also the objective of Yousef's \textit{et al} study on cyber-physical threats on robotic platforms~\cite{yousef2018analyzing}.

In general, we see a research gap in terms of addressing the physical dimension in robotic operation from a security and safety point of view. This becomes even more evident when analyzing the most widely used robotic frameworks. Among them, the Robot Operating System (ROS) has become a standard across both industry and academia. Multiple researchers have studied the security flaws of ROS~\cite{demarinis2019scanning}, and proposed different approaches to address these issues~\cite{amini2018cryptoros}. Moreover, many of these are being mitigated in the newest version, ROS2~\cite{kim2018security}. However, these efforts are again directed at securing ROS as a distributed and networked system, and not from the point of view of a robotic framework meant for robots to interact with their environment. While it is highly important to provide security from the data flow point of view, we direct our efforts in this paper towards the gap in securing and validating the way robots are controlled and interact with their environment.

In this work, we focus on providing a framework for validating data integrity. Other types of cyberattacks such as denial of service attacks, in which the communication channels are congested, are not considered. Nonetheless, it is worth noting that our proposed approach can provide some benefits even in such situations. While the communication channel utilized to transmit the encoded commands to the robot might be known to an attacker, the sensor data or inputs triggering the different actions are unknown even to the robot itself, if multiple possibilities exist. Therefore, our framework also provides partial mitigation for other types of cyberattacks where the channel utilized to trigger a robot's actions might be disguised within the encoded instruction graph sent to the robot before the mission starts.












\section{Encoded Instruction Graphs}

In this section, we describe the main framework components and how it can be applied in different scenarios.

\subsection{Encoding Robotic Instructions}

We follow up on the instruction encryption ideas from~\cite{ferrer2019secure}, where missions instructions are given to a robot by encoding combinations of sensor inputs and a set of robot actions. %
We do not consider explicitly multi-robot cooperation but instead focus on describing robust options for encrypting and decrypting mission instructions. Moreover, we also evaluate the performance degradation inherent to encrypting data when compared to standard robotic operation, avoiding random behaviour. In order to do that, the first step is to not only encode a set of actions and features from sensor data, but also some other variable that enables a \textit{hash search}, a trial-and-error process in which a robot does not need to be able to reproduce a specific hash but instead can try multiple hashes until finding a match. An example of this is the addition of a spatial or temporal component. The second step is then to define not only a series of encoded actions but also encoded states, which can be defined based on a combination of variables (e.g., position, time, sensor data or other external inputs). By encoding both states and actions, we can then wrap the set of encoded information into a graph structure, such that the encoded information in an edge of the graph gives the robot information about how to arrive to a different state or process. We call this an encoded instructions graph. A sample encoded instructions graph is shown in Fig.~\ref{fig:sample}. In this graph, the initial instruction is encoded into a hash $H_1$, which the robot is able to decode by combining a certain predefined action with some sensor data. Most of the nodes in the graph represent states, with the majority of the nodes in this example being defined by a position and some sensor data. However, the information that nodes encode is not restrictive, as it can be both actions or states. The edges, however, should encode information that enable the robot to transit between nodes, and therefore should include some type of action or external input. An edge can also be empty, i.e., if the robot can gather enough information to decode a different node without any intermediate step. In the example in Fig.~\ref{fig:sample}, the initial node triggers an action by the robot whenever it is able to acquire some certain sensor data. It can then proceed to two different states in which it must to be able to reproduce both its position and sense a different variable. The encoded information in the second node, $H_2$, can then be decoded after a certain time, which can for example be used as a failsafe to go back to the initial state if the sensor data defining $H_3$ cannot be acquired in time. In practice, the robot is not aware of the type of information encoded in each hash, and must therefore perform a continuous trial and error process to try to reproduce the hashes by all the different means it has been preprogrammed for. In our experiments, we show that this process of trial-and-error has a mostly negligible impact compared to the computational cost of extracting features or processing sensor data in standard robotics algorithms. In any case, the process of deciding how to define the encoded instructions is not trivial, as they must be reproducible, while concise enough to avoid data mismatches.


An encoded instruction graph as described above is a directed graph. For a mission that has only one possible solution and where each step is followed by one and only one other step, then the graph is reduced to a path or linear graph. In many cases, the graph will be acyclic. This happens when there are multiple options to complete a mission, but once a set of steps is taken then the same ones cannot be taken again. For instance, in a manufacturing process, the order in which a set of parts are moved to a working bench might not matter, yet every part must be moved exactly once. In a general case, the graph can be arbitrarily complex and contain any number of cycles. For instance, a reconnaissance mission in which a robot has to navigate an objective area without any specific order could have multiple cycles. Higher mission control embedded at the robot should then be able to understand these more complex graphs and provide a planning strategy that is not directly sent by the mission controller. An example of this will be given in our experiments.




\subsection{Validation Modalities}

The proposed approach can be extended to multiple scenarios, as the encoded information cannot only be a set of predefined actions and features extracted from sensor data, but also other external inputs, variables defining the state of the robot, or even timing constraints. The possibility of utilizing external inputs is particularly interesting as it enables secure and secret multi-robot cooperation but also new ways of defining under which conditions human-robot interaction can happen. Since the inputs can already be encoded, the information exchanged between robots or utilized as external signals triggering robot actions can be defined in a way that they are totally meaningless and only usable when combined with other data. Therefore, if the data is spoofed or a third party gains access to this communication medium, no real data is actually compromised. Different possibilities for encoding and decoding instructions are shown in Fig.~\ref{fig:actions}, and described in more detail in the following subsections.






\subsubsection{Independent Validation}

The simplest approach is to encode mission instructions individually and independently. In this case, an encoded instruction set can be sent to the robot, similar to the approach followed in~\cite{ferrer2019secure} but where only the leaves of the Merkle tree would be sent. This set of instructions does not define a graph structure and does not represent the main interest of this paper. However, these instructions can be utilized as the root of an encoded instruction graph, or as a trigger for starting a parallel process at the robot.

An additional layer of security can be added by introducing time or spatial constraints.
Time constraints (e.g., introducing a timestamp in the hash) provide an extra layer of security against attacks that could spoof the encoded data and reproduce it later, even if the data itself cannot be decoded. 
Similarly, spatial constraints can be added by including the robot's location in the hash. This, however,
only prevents the replication of the robot's behavior in other locations.



\subsubsection{Iterative Validation}

An iterative validation happens when a robot is able to validate its own actions. This particular modality will be the case studied in the next sections with the introduction of an encoded navigation graph.

Encoded instruction graphs defining an iterative validation process can contain different types of encoded data in their nodes and edges. For instance, sensor data can be encoded in the graph nodes, which serve the purpose of validating the process. Additionally, this sensor data can encode other information, such as positional information or time information that can be utilized as a part of the control loops at the robot. Then, the actual instruction for the robot to move towards the next step is encoded in the edge of the graph, which encodes both the data in the current node being validated and the action or actions that will enable the robot to decode the next node. An illustration of this process is shown in Fig.~\ref{fig:iterative}. 

\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{fig_graphs/iterative_cr_v3.pdf}
    \caption{Illustration of an iterative validation process.}%
    \vspace{-1em}
   
    \label{fig:iterative}
\end{figure}



\subsubsection{Multi-Robot Simultaneous and Mutual Validation}

As we have mentioned earlier, one significant scenario where this validation framework can be applied is in multi-robot cooperative behavior. Complementing the ideas proposed in~\cite{ferrer2019secure}, we are now also able to break down a mission in two disjoint parts that can be given to two different robots. An example of this is shown in Fig.~\ref{fig:collaborative}, which illustrates a collaborative inspection process. Each encoded instruction is defined with the combination of different signals or parameters, or a subset of them. First, data triggering an action can be a set of features extracted by the robot from its own sensor data, but we can now also differentiate between sensing the environment and sensing the behavior of the other robot. Second, the two or more robots can also exchange messages in order to trigger each other's actions. These messages can be meaningless to both of them, and also include environment data for an extra layer of robustness.





\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{fig_graphs/collaborative_inspection_v3.pdf}
    \caption{Illustration of a collaborative inspection process where robots only have partial instructions.
    \label{fig:collaborative}
\end{figure}






\section{Problem Definition}








\section{Encoded Navigation Graph}
\label{section.EncodedNavigationGraph}

One of the most fundamental ways in which a robot interacts with its environment is by navigating it. Maps have long been utilized for autonomous navigation and exploration in mobile robots to increase the robustness of long-term autonomous operation~\cite{hilnbrand2019roadwaygeometries, sobreira2019mapmatching, qingqing2019multi}. Maps or landmarks provide robots means for localization in a known reference frame, while enabling the calibration and adjustment of on-board odometry and localization algorithms.


Landmark-based navigation has been successfully implemented in various mobile robots with quick response (QR) codes~\cite{andersen2013qrcalibration, zhang2015qrnavigation, nazemzadeh2017qrfusion} or other identifiable images\cite{zamir2010accurate, sattler2016efficient, thoma2019mapping}, wireless sensor networks~\cite{cheng2011wsn}, or ultra-wideband (UWB) markers~\cite{almansa2020autocalibration, shule2020uwbbased, song2019uwb}, among others including IMU fusion~\cite{nazemzadeh2017qrfusion}, or topological maps in for infrastructure-free navigation~\cite{gadd2015warehouse}. When utilizing landmarks that are already encoding certain information, such as QR codes or other text representations, is that additional information can be embedded into the landmarks. In an industrial scenario, this can be utilized to provide further instructions for robots~\cite{qin2017sorting}. 



In order to analyze the viability of this idea and discuss the potential directions for solving the research questions defined in Section~I, we consider the most essential aspect of a robot's interaction with its environment: \textit{the navigation}. Therefore, we capsulize the research questions to more concrete considerations regarding the navigation of autonomous robots:

\begin{enumerate}
    \item Is it possible to provide a description of the environment (e.g., a map or a set of landmarks and how to travel between them) to an autonomous robot, in a way that the robot is unable to understand the map until it starts navigating, and such that it can only decode the information in that map if a series of conditions on how it sees its environment are met?
    \item Is there a way of defining navigation instructions for an autonomous robot such that any modification of those instructions automatically renders them unusable ensuring that if wrong sensor data is fed to the robot's controller, the instructions cannot be followed?
\end{enumerate}











\subsection{Encoded Graph Definition}

Rather than modeling a map of the objective exploration area and utilize it for navigation, we utilize a landmark-based navigation graph that encodes the position of the different landmarks and the navigable directions between landmarks. In this graph, each vertex represents one encoded position in the map, and each edge represents a straight or unique path between two positions. By unique we mean a path that might not be straight but such that the robot can realistically follow.
A sample map and the corresponding encoded navigation graph are illustrated in Figure \ref{fig:sample_map}. In this and latter sections, we utilize the following notation. A graph is an ordered pair $\mathcal{G}=(V, E)$, where $V$ represents a set of vertices, and $E$ represents a set of edges associated with two distinct vertices, i.e., a set of tuples $\{(V_i,V_j) \:|\: V_i,V_j \in V\}$. We consider a directed graph, were the order of these tuples matters.


The most straightforward approach to landmark encoding is to define the hash of a position given its coordinates $\vec{r}\in\mathbb{R}^3$. Thus we would define $H_i=H(\vec{r}_i)$. 
In order to ensure that hashes will be reproducible, the coordinates need to be given in a coarse grid with a resolution that is dependent on the accuracy of the robots' onboard odometry.

If the environment is accessible a priori, elements can be installed that facilitate the localization of robots when they are nearby, such as QR codes, or Bluetooth/UWB beacons.
The QR codes contain hashed data and can encode additional information, for example, instructions for a robot to operate in a given room or area. An alternative approach is to utilize the environment geometry and topology. The coordinates of the features can still be utilized to define their hash without using a predefined grid. Rather than having a robot utilizing its own or near position to calculate the hash, it can calculate it based on the coordinates of a position that depends on the robot's current local environment. 




    
    

    






\subsection{Deployment and Navigation}

We assume that the position where a robot is deployed is either known in an absolute reference frame, or utilized as a common reference in the robots' local coordinate system. If only local references are utilized, these must have a common orientation. The initial position is encoded with a hash but also known to robots.

In the encoded navigation graph, each edge in the graph is given two hashes, as the robots might reach these from different directions. Therefore, the adjacency matrix containing the edge hashes shown in Fig.~\ref{fig:sample_map} is not symmetric. 
Only minimal information about the local environment required for navigation purposes needs to be stored at the robots. Odometry-only (map-free) navigation, when possible, would be preferred to minimize the amount of raw information that robots store.


The directions between features, or the initial position and near features, is encoded in a way that can be matched by robots on a basis of trying multiple possible directions until finding one that produces the corresponding hash. The edge hashes are calculated on a trial-and-error basis, and thus they can be defined with an arbitrary division of the $[0, 2\pi)$ interval. However, this decision must take into account the trade-off with the inherent computational overhead. Furthermore, not all the navigable directions are necessarily selected, and therefore the real topology of the objective environment can be, to some extent, hidden. In addition, multiple features can be selected within a single room or small area, but even if all detectable at the same time, a fully connected subgraph does not need to be generated within the navigation graph. In general terms, there is a trade-off between the number of actual connections between features that are encoded in the navigation graph, and the robustness of the navigation in the event of robots not being able to reproduce a certain subset of landmark hashes.


\subsection{Landmark-based Localization}

The accuracy of the feature's position directly affects the error tolerance for the odometry method utilized for navigation when no landmarks are detected. In order to cope with the odometry error, if it can be estimated then it can be taken into account to calculate the hashes from the position of landmarks, following a trial-and-error approach within a certain spatial area around the landmark. The number of trials that a robot needs to perform depends on the accuracy of the odometry method utilized, and the granularity of the grid utilized to define the position of the landmarks and calculate the hashes. Additionally, the possibility of the robot identifying a wrong landmark that is nearby must be taken into account. Therefore, there is a trade-off between accuracy and robustness with multiple factors to take into consideration.










\section{Methodology}

In order to test the feasibility of the encoded navigation approach presented in this paper, we have run a series of simulations and experiments. In these, we analyze the overhead and performance impact from calculating hashes and utilizing the encoded navigation graph. In all cases, we make the assumption that the environment is known to the mission controller. We have devised two types of application scenarios in which we test the proposed framework.


First, we consider an environment where only robots operate. In this case, we have simulated the interior of a building with empty rooms.  For
this scenario, we utilize a simulation environment, in which we encode geometric features in the navigation graph: doorways, corners and rooms. For the simulations, we consider a fully automated environment with no dynamic obstacles and known geometry. This can be applied, for instance, to logistic warehouses where only autonomous robots operate. It can also be applied to autonomous cleaning machines operating at night, or, in general, any scenario where the environment does not change significantly over time. In our simulations, the robot relies on a two-dimensional laser scanner for feature detection.

Second, we consider a real office setting with a dynamically changing environment, people moving in it and a wide variety of objects populating the different rooms. The experiments are carried out relying on visual markers that can be placed in multiple fixed locations. For
this application scenario, real experiments are carried out in an office environment with people and a variety of furniture across different rooms. Because of the large amount of desks, chairs and other equipment, detecting geometric features from the environment would render irreproducible hashes and multiple situations in which features can not be detected due to either objects or people blocking the field of view of sensors. To tackle this issue, we have utilized QR codes as markers to encode the landmark positional information.


\subsection{Simulation Environment}

The proposed encoding approach has been implemented within the Robot Operating System (ROS) in Python. ROS is the current de-facto standard for production-ready robot development~\cite{quigley2009ros, koubaa2017robot}. The simulations were carried out within the ROS/Stage environment. A TurtleBot 3 is simulated with a 2D lidar and wheel odometry. The robot is set to explore an indoor environment with a floorplan illustrated in Fig.~\ref{fig:simulation_results}\,(a). The environment is $40\times40\,m^2$, and the robot has a circular shape with a diameter of $0.35\,m$. The simulated environment contains 9 rooms with a single entrance and 6 more spaces and corridors in between. The starting exploration position of the robots is near the main door, in the bottom-left. The 2D lidar has a field of view of 270\textdegree~and produces 1080 samples (0.25\textdegree~resolution) in each scan, with a scan rate of 1\,Hz. This work presents a proof of concept, and therefore we do not study the effect that different odometry methods have in the exploratory mission. Instead, we utilize wheel odometry and vary its error to study the impact that the corresponding computational overhead has due to a larger number of hashes being calculated.

\begin{algorithm}[t]
    \kwCbk {
        \par
        \kwCal {
            \par
            $\textbf{F} = getF(data)$; \hfill \small{// Orientation-ordered $F$ set} \\
            $\textbf{F}_{cv} = getCv(\textbf{F}) \subseteq \textbf{F}$; \hfill \small{// Set of concave features} \\
            $\textbf{F}_{cc} = getCx(\textbf{F}) \subseteq \textbf{F}$; \hfill \small{// Set of convex  features}  \\
        }
        \kwDef {
            \par
            $\textbf{H} = []$; \hfill \small{// List of hashes}
        }
        \ForEach{$fp_i,\:fp_j\:\in\:\textbf{F}_{cv}$} {
            \If{$\Vert fp_i - fp_j \Vert < \delta_{dw}$} {
                $H.append(doorwayHash(fp_i, fp_j))$\;
            }
        }
        \ForEach{$fp_i\:\in\:\textbf{F}$} {
            \If{$ fp_{i+j}\in\textbf{F}_{cx}\:\:\forall j \in \{-1,0,1\} $} {
                $H.append(roomHash(fp_{i\text{-}1},fp_{i},fp_{i\text{+}1}))$\;
            }
        }
        \ForEach{$fp_i\:\in\:\textbf{F}_{cv}$} {
            \If{$isCorner(fp_i) \:\&\&\: notDoor(fp_i) $} {
                $H.append(cornerHash(fp_i))$\;
            }
        }
        \small{// Utilize any matching hashes to update the robot's} \\
        \small{// position with respect to the global reference frame} \\
        \If{$\exists\:h\in\:H\:\vert\:h\in\:NavGraph$} {
            $updateAbsolutePosition(H))$; \hfill \small{// Use matching hashes}
        }
    }
    \caption{Feature Extraction and Hash Calculation}
    \label{alg:features_and_hashes}
\end{algorithm}

\subsection*{Feature Extraction}

In the simulation experiments, we utilize three types of features to localize the robot and navigate the environment: doorways, concave corners and rooms. These are defined from the same set of $F$ feature points which we denote as Features of Interest $FoI = \{ fp_1, \dots, p = fp_F \}$, where $fp_i\in\mathbb{R}^3$. The feature extraction process is outlined in Algorithm \ref{alg:features_and_hashes}. 
The $NavGraph$ variable stores a list of hashed positions as well as an adjacency matrix with the edge hashes. A sample of this is shown in  Fig.~\ref{fig:sample_map}, subfigures (c) and (d). The function $search()$ calculates a certain number of hashes over a predefined area around the identified feature until it either finds a matching hash from $NavGraph$ or ends the search unsuccessfully. This function ensures that the hashes are reproducible even if odometry error accumulates over the inter-landmark navigation. The search area is defined based on the expected odometry error as well as the granularity of the grid utilized to define the hashes. Finally, the function $updateAbsolutePosition()$ takes the matching hashes as arguments, calculates the relative position of the robot with respect to the landmarks that have been identified and utilizes the known position of the landmarks (which is encoded in the hashes) to recalculate its own position and restart the odometry estimation.

\vspace{0.12cm}
\subsubsection*{Doorways} 
    We define doorways as any set of two concave feature points that are within two predefined distances $(\delta_{dw,min}, \delta_{dw,max})$ from each other. In our simulations and experiments, we set these distances to $\delta_{dw,min}=1.2\,m, \delta_{dw,max}=2.5\,m$. Note that these feature points might not be consecutive if we consider the ordered set of feature points by orientation.
    We define the corresponding waypoint to be encoded according to~\eqref{eq:door}:
   
    \begin{equation}
        H_{dw}(fp_i, fp_j)= H\left(\text{"doorway"},\frac{fp_{i}+fp_{j}}{2}, \angle fp_{i}fp_{j} \right)
        \label{eq:door}
    \end{equation}

\vspace{0.12cm}
\subsubsection*{Corners} 
   
    For each concave corner not in a doorway, we define its corresponding hash with~\eqref{eq:corner}:
   
    \begin{equation}
        H_{cv}(fp_i)= H\left(\text{"corner"}, fp_{i}, \angle fp_{i}\right)
        \label{eq:corner}
    \end{equation}
    where $\angle$ represents the orientation of the normal vector to the wall surface at the position of the corner.

\vspace{0.12cm}
\subsubsection*{Rooms} 
   
    A room waypoint is defined as the centroid of any three consecutive convex points, calculated as the arithmetic mean of their positions. 
   
    To reduce the probability of having a mismatch in rectangular rooms where two consecutive subsets of three convex corners are visible by a robot, we add the area $\Delta$ of the triangle that the points define: 
   
    \begin{multline}
        H_{dw}(fp_i, fp_{i+1}, fp_{i+2})= \\
        H\left(\text{"room"},\dfrac{fp_{i}+fp_{i+1}+fp_{i+2}}{3}, \Delta_{i,i+1,i+2} \right)
    \end{multline}

\subsection{Real-Robot Experimental Settings}

The experimental environment is shown in Fig.~\ref{fig:experiment_results}\,(a). For the experiments, an EAIBOT DashGo D1 has been utilized. We have installed a 16-Channel Leishen 3D Lidar, an SC-AHRS-100D2 IMU, and a Logitech c270 USB camera. The DashGo provides wheel odometry from its differential drive system. The 3D lidar is utilized to accurately localize the landmarks and provide ground truth odometry. The camera is utilized to detect the QR codes and extract the encoded information in them. Figure~\ref{fig:ros_nodes} show the implementation diagram with different ROS nodes. The 3D lidar odometry and mapping are adapted from the LeGo-LOAM-BOR package~\cite{legoloam2018}. The QR code decoding node has been written in Python using OpenCV and the Zbar library. The hash based localization node utilizes the QR codes for localization when available and the wheel and inertial odometry as an estimation between landmarks. The QR codes utilized during the experiment are of known size (12\,cm by 12\,cm), and the localization node has been calibrated to map the size in pixels of a detected QR code in the camera to the distance to it. The localization also takes into account the relative orientation of the QR code.

\begin{figure}
    \centering
    \includegraphics[width=.48\textwidth]{fig_new/ROS_Nodes_light_color.pdf}
    \caption{Data flow in the experiments. Each box represents a ROS Node which has been implemented either in C++ or Python. The outputs are the ground truth, odometry (odom) error and has-based localization error (loc. error).}
    \label{fig:ros_nodes}
\end{figure}


\subsection{Feature Hashing}

We utilize SHA3-256 for hashing~\cite{czajkowski2017quantum}, which generates 32~byte hashes. It takes an average of under 500~ns on an Intel(R) Core(TM) i5-6200U CPU with the pysha3 implementation in Python. If additional security is required against offline attacks on exposed hashes, other hashing algorithms such as Bcrypt~\cite{sriramya2015providing} can be utilized. Bcrypt needs around 300~ms to generate a hash with the same CPU. However, there is a trade-off between security and real-time operation as robots need to calculate multiple hashes per lidar scan. We believe that, in most applications, SHA3-256 is enough and can be utilized even in resource-constrained devices.

\begin{figure}
    \centering
    \includegraphics[width=0.42\textwidth,height=0.23\textwidth]{fig_new/sim_floorplan.pdf}
    \caption{Floorplan of the simulation environment. All doors, rooms and corners are utilized as encoded landmarks.}
    \label{fig:sim}
\end{figure}


\begin{figure*}
    \centering
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{fig/sm_paths_TEST121212.tex}}
        \caption{Ground truth and estimated path during simulation.}
    \end{subfigure}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{fig/sm_errors_TEST121212.tex}}
        \caption{Localization error over the simulation time.}
    \end{subfigure}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{fig/error_boxes.tex}}
        \caption{Odometry and hash-based localization error for different odometry noise levels.}
    \end{subfigure}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{fig/time_boxes_log.tex}}
        \caption{Execution time of the different processes (feature extraction in red, hash search and matching in blue) for a varying grid size.}
    \end{subfigure}
    \caption{Simulation results. Subfigures (a) and (b) show the reconstructed path and errors, respectively, with ground truth (GT) wheel and inertial odometry (O), only doorway hashes (D), and all features: doors(D), rooms (R) and concave corners (CC). Subfigure (c) shows the odometry and hash-based localization errors for different odometry noise levels. Finally, (d) shows the execution time distribution for the feature extraction (red) and hash matching (blue) processes, where the grid size represents the search space when trying to find a hash match.}
    \label{fig:simulation_results}
\end{figure*}

\begin{figure}
    \centering
    \includegraphics[width=.42\textwidth, height=0.3\textwidth]{fig/3dmap_cr.png}
    \caption{3D point cloud of the experiment environment utilized as ground truth in our experiments. The path of the robot is shown with colored points, where red represents the start of the mission and purple the end.}
    \label{fig:my_label}
\end{figure}

\begin{figure*}

    \centering
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{exp/experiment_paths_xs_v2.tex}}
        \caption{Estimated path and ground truth during the experiment.}
    \end{subfigure}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{exp/experiment_errors_xs.tex}}
        \caption{Localization error over time.}
    \end{subfigure}
    
    $ $ \\[+6pt]
    
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{exp/experiment_qr_errors_xs.tex}}
        \caption{Localization error when a QR code is in sight.}
    \end{subfigure}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{exp/times.tex}}
        \caption{Execution time for the different processes.}
    \end{subfigure}
    
    \caption{Experiment results. Subfigures (a) and (b) show the reconstructed path and errors, respectively, with ground truth (GT), wheel and inertial odometry (Odom) and hash-based localization (Hash). In (c), we show a scatter plot with the localization error every time that a QR code is within the field of view of the camera. Finally, (d) shows the execution time for the QR code extraction when it is within field of view (QRV), for the QR code extraction process globally and independently on whether there is or not a QR code visible (QRG), for the hash matching algorithm when a QR code is within field of view (HQR), and for the hash matching algorithm over the global mission (HG).}
    \label{fig:experiment_results}
    
\end{figure*}


\section{Simulation and Experimental Results}

We have carried out a series of simulations with one and multiple robots to evaluate mainly the cost of utilizing hash matching for localization and navigation, but also the impact on accuracy of the encoded landmarks.

\subsection{Metrics}

In order to evaluate the simulation results, we measure the absolute localization error of the robot with odometry only and hash matching. Furthermore, we analyze the distribution of the computational load among the different tasks that the robots are carrying out: feature extraction, hash calculation and hash matching. In the simulations, we also measure the effect of the odometry-based localization noise and the choice of spatial granularity for landmark positions.

\subsection{Simulation Results}

The aim of the simulations is to prove whether our encoded landmark localization and navigation scheme is viable and adds a significant computational overhead or not.

Figure \ref{fig:simulation_results}\,(b) shows the path recovered from odometry measurements and hash-based localization with doorway hashes only, and all three types of hashes, together with the ground truth (GT). The data is recorded over 150\,s; the translation odometry noise is set with $\sigma_t=0.03$, and rotation noise with $\sigma_r=0.05$. The absolute error of each of these paths is given in Fig.~\ref{fig:simulation_results}\,(c). Because the doorway-type landmarks are predominant in the chosen simulation environment, the localization error does not decrease significantly when also considering rooms and concave corners. 

In the simulated environment, we have predefined the position of landmarks with an accuracy of $0.1$\,m. Therefore, when analyzing the errors in Fig.~\ref{fig:simulation_results}\,(c) and Fig.~\ref{fig:simulation_results}\,(d), any values below $0.15$~m represent virtually zero error. Fig.~\ref{fig:simulation_results}\,(d) shows that the localization method is robust even when the odometry error increases significantly ($\sigma_t=0.05$). However, there is a limit, around $\sigma_t=0.06$, for which the size of the environment is big enough that the robot is unable to match landmark hashes due to odometry error. In order to calculate these hashes, we assume an error tolerance with respect to its estimated position of $\pm0.5$\,m, independently of the size of the grid utilized to locate the landmarks and generate the hashes.

Regarding the computational overhead necessary to calculate the hashes, estimate the robot's position, and perform path planning accordingly, Fig.~\ref{fig:simulation_results}\,(e) shows the distribution of computational time utilized to extract the set of features, or points of interest, from the raw lidar data and the distribution of computational time utilized in calculating and matching hashes. For an error tolerance of $\pm0.5$\,m, the graphic shows situations in which the robot tests up to 9, 25, 121, 441 and 1681 grid positions, respectively. The search for a hash match is gradually done in a spiral manner around the estimated position and within the aforementioned error tolerance. These results show that even with fine-grained grid search, in average the time required to localize the robot based on hashes is two orders of magnitude smaller than the time required to extract features from lidar data. In the worst-case scenario, the time required can be comparable, with an equivalent order of magnitude for both hash matching and feature extraction. 


\subsection{Experiment Results}

Figure \ref{fig:experiment_results}\,(b) shows the path recovered from odometry measurements and hash-based localization (QR codes). The error in the odometry is significantly higher than in the simulation experiments due to a drift in the yaw measurements. However, the translational odometry error is much smaller. The hash-based localization is able to correct this orientation whenever a QR code is within the field of view, and therefore it does not suffer from the yaw drift. The maximum hash-based localization error that we observed was of 41.3\,cm. This allowed the utilization of a fine grid of 2\,cm for calculating the landmark hashes. We set a $1\,m^2$ hash search area around the estimated location which was enough in this case.

A total of 23\,QR codes were installed in the office environment, and the tests were done with a small number of persons in their offices. Out of those, 17\,QR codes were utilized by the robot during its navigation. The execution time of the hash matching algorithm was on average over one order of magnitude smaller than the time required to extract the QR codes from camera images. Thus, the overhead was mostly negligible. Only in a reduced number of occasions was the latency of these two processes comparable, as Fig.~\ref{fig:experiment_results}\,(e) shows.



\subsection{Viability and Usability}

We have seen that the computational overhead added when encoding landmarks is mostly negligible. Thus, our approach could be incorporated on top of many existing navigation and localization schemes, whether they are landmark-based or not, to increase the level of security if the error tolerance allows. 

This approach has additional uses when more than one robot is taken into consideration. In multi-robot cooperation, different robots can share their plans, progress or position (based on the navigation graph only) with others by utilizing the same hashes or parts of them. This would reduce the possibility of raw data being exposed but also virtually eliminate the options for attackers or byzantine agents to affect the mission, as has been shown in~\cite{ferrer2019secure}.


























\section{Discussion}




\section{Conclusion and Future Work}

Security and safety in robotics are crucial aspects to take into account with the current surge of autonomous robots penetrating multiple aspects of our society and the increasing interaction between robots, and between robots and humans. In this direction, further research needs to focus on the validation of data at the different layers of robotic systems, and in particular the validation of the interaction of a robot with its environment. This interaction often starts with navigation, which has been the main aspect studied in this paper.

Navigation and localization in autonomous robots require large amounts of raw data for long-term operation, either given a priori by a mission controller or acquired by robots while performing their missions. In addition, validating the integrity of both mission instructions and sensor data without any external feedback is an open problem. We have presented a framework that enables robots to validate both the correct operation of their onboard hardware and sensors, and the integrity of information received from an external controller.

In particular, to the best of our knowledge, this paper introduces and evaluates the first end-to-end validation framework that focuses on navigation and localization with encoded landmarks, which allows robots to effectively perform their missions while performing end-to-end validation of information. We have shown that utilizing an encoded navigation graph adds only a negligible computational overhead even when high-accuracy positioning is required.

The end-to-end validation scheme demonstrated in this work for navigation tasks can be naturally extended to cover virtually all domains of robotic operation. In future work, we will focus our research efforts towards experimentation in more relevant environments, and in particular industrial settings. We will aim at extending this approach to other interaction forms between a robot and its environment, from multi-robot collaborative assembly to human-robot interaction and control.


