slam.md

Here is a general overview of the SLAM algorithm, drawing from the sources, presented as a cheat sheet: SLAM (Simultaneous Localisation and Mapping) is an algorithm with the goal of estimating the trajectory of a robot or sensor while simultaneously building a map of the environment. • It addresses the problem that estimating a map and estimating the robot's pose are interdependent. • SLAM is often called a "chicken or egg" problem, since knowing the poses makes mapping easy, and knowing the map makes localisation easy. Inputs: • A sequence of control commands, denoted as U from time step 1 to time step T. These can be raw velocity commands or odometry readings. • Sensor observations, denoted as Z, from sensors like laser range finders or cameras, providing information about the environment, such as bearing and range information to landmarks. Outputs: • A map of the environment (m), typically a set of landmark locations. These landmarks are identifiable objects that the robot can detect with its sensors. • The path of the robot (x), representing the robot's position (x, y) and orientation at different points in time. Online SLAM focuses on estimating the robot's current pose, ignoring previous locations. SLAM approaches can be categorised into three paradigms: 1. Kalman Filter (EKF) based methods: ◦ Utilise the Extended Kalman Filter algorithm to estimate the robot pose and landmark locations. ◦ EKF is a recursive filter consisting of two steps: prediction and correction. ▪ Prediction: Uses control commands to predict the new state (pose) of the robot. ▪ Correction: Uses sensor observations to correct the predicted state. ◦ The Kalman Gain (K) is computed to weigh the predicted belief and sensor properties. A higher Kalman Gain means more trust is given to sensor observation. ◦ The state space includes the robot's pose (x, y, theta) and the landmark locations. ◦ Requires defining a non-linear function G that describes the transition from a given state and control command to a new state and computing its Jacobian. ◦ Needs an observation function H and its Jacobian. ◦ Initialization requires defining the mean vector and covariance Matrix. ◦ The update step involves computing the difference between expected and obtained observations. 2. Particle Filter based methods: ◦ Represent the state space using a set of samples or particles. ◦ Each sample represents a possible state of the system, and the probability distribution is approximated by the distribution of these samples. ◦ Key steps: proposal distribution, correction (weighting), and resampling. ◦ Monaco Localization (MCL) uses particles to represent the pose of the robot (x, y, theta) and uses the motion model as a proposal distribution. ◦ FastSLAM is a particle filter approach to SLAM that separates the estimation of the robot's trajectory from the estimation of the map. Each particle maintains its own map. ▪ Uses a sample-based representation to represent the trajectory of the robot. ▪ The proposal distribution is typically the motion model. ▪ Importance weights are computed based on the difference between the expected and obtained observations. ▪ Low variance resampling is used. ◦ Grid-based SLAM uses a variant of FastSLAM to build grid maps. ▪ Each particle represents a possible trajectory of the robot and maintains its own map. ▪ Scan matching can be used as a pre-correction step to improve the pose estimate. 3. Graph-based approaches: ◦ More modern systems use graph-based approaches due to their flexibility. ◦ Involves creating a graph where nodes represent robot poses and landmarks, and edges represent constraints between them. ◦ Aim to reduce the sum of squared errors. ◦ A front end is used to determine if a constraint is likely to be correct. continue

Here are some more details on aspects of the SLAM algorithm, drawing on the sources: EKF SLAM Details: • The prediction step in EKF SLAM only affects a subset of the variables, as motion commands primarily change the robot's position and not the landmark positions. • Implementing the prediction step requires defining a non-linear function G to move from a given state and control command to the new state, as well as computing its Jacobian. • The correction step involves computing the Kalman gain K to determine a weighted sum based on the robot's certainty about its predicted belief versus the sensor properties. • R and Q matrices represent covariance change for the whole state space and measurement covariance, respectively. • Loop closing in EKF SLAM involves revisiting a known area, which can be challenging due to ambiguities and symmetric environments. • EKF-based SLAM can face computational problems for large-scale maps, which has led to sub-mapping techniques. Particle Filter SLAM Details: • The particle filter uses samples to represent the posterior and the important sampling principle to update a belief. • The prediction step involves drawing samples from a proposal distribution using motion odometry, while the correction step uses observations. • The more samples, the better the estimate. • The algorithm involves sampling from the proposal distribution, correction to account for the difference between proposal and target distribution, and a resampling step. • FastSLAM uses a set of samples to represent the path posterior, with the key insight that the mapping process is independent for each sample. • In FastSLAM, each particle maintains only the current pose of the robot and landmark locations, as past trajectories are not revised. • The importance weight in FastSLAM is computed as the target distribution divided by the proposal distribution. • A Gaussian distribution is used, taking into account the current observation minus the expected observation. • Data association can be done on a per-particle basis, which helps in solving the data association problem. • A limitation of some particle filter approaches is the assumption of a static environment. • Grid-based SLAM with Rao-Blackwellized Particle Filters uses scan matching to improve pose estimates before applying the particle filter. • An improved proposal distribution uses the current observation in the proposal distribution of the particle filter. General SLAM Considerations and Approaches: • Motion Model: describes the robot's movement. • Observation Model: describes how to interpret observations. • Active SLAM: the robot makes its own decisions about where to go in order to build a good map of the environment. • Passive SLAM: an incoming data stream is used. • Anytime/Ayspace SLAM: an algorithm that works within given time and space constraints. • Loop Closure: when the robot revisits a known area. • Ambiguities in the environment must be taken into account to build accurate maps. • Homogeneous coordinates can be used to represent transformations, particularly with bearing-only sensors like cameras. Open Issues in SLAM: • Dealing with dynamic environments. • Systematically changing environments. • Seasonal changes. • Online solutions for larger environments. • Lifetime operation. • Resource-constrained systems. • Failure recovery. • Exploiting prior information. continue

Here are further details about SLAM, including specific algorithms and techniques, and limitations: SLAM Summary • SLAM estimates the path a sensor takes and a map of the environment using sensor observations and controls. • The problem can be simplified if either the poses or map are known. • SLAM implementations must choose a map representation. It could be: ◦ A set of 3D landmark locations. ◦ A dense grid map. • Frameworks must decide whether to estimate the full trajectory or only the current pose. Extended Kalman Filter (EKF) • Algorithm: This filter recursively estimates the state of a system. • Two Steps: ◦ Prediction Step: Predicts the next state based on the previous state and control inputs. ◦ Correction Step: Corrects the prediction based on new sensor observations. • Jacobians: EKF uses Jacobian matrices to linearise non-linear functions. Particle Filters • Sample-Based Representation: Approximates probability distributions with a set of samples or particles. • Proposal Distribution: Samples are drawn from this distribution to advance to the next state. • Correction (Weighting): Adjusts particle weights to account for the difference between the proposal and target distributions. • Resampling: Eliminates particles with low weights and duplicates those with high weights to focus on high-probability areas of the state space. • Monte Carlo Localisation (MCL): A special instance of particle filters used for robot localisation. • FastSLAM: A particle filter approach where each particle maintains its own map. Loop Closure • Definition: When the robot revisits a known area after a long traversal. • Challenge: Requires careful data association to avoid ambiguities, especially in symmetric environments. Frontends • Role: Used to determine if a constraint is likely to be correct, helping to manage ambiguities in the environment. Addressing Ambiguities • Ambiguity: Addresses the challenge of building accurate maps in ambiguous environments. • Iterative Closest Point (ICP): An algorithm sensitive to initial guesses, often used in SLAM frontends. Can be improved by arranging scans into maps or separating local perceptions. Feature descriptors can help find good estimates for loop closures. Motion and Observation Models • Motion Model: Describes how the robot moves based on control inputs. • Observation Model: Describes the expected sensor measurements given the robot's pose and the map. Homogeneous Coordinates • Use: An alternative to Cartesian coordinates for expressing transformations. • Bearing-Only Sensors: Useful with sensors that only measure orientation, like cameras. Open Issues and Future Directions • Dynamic Environments: Handling changes in the environment. • Systematic Changes: Exploiting patterns in regularly changing environments, such as seasonal changes. • Online Solutions: Scaling SLAM to larger environments in real-time. • Lifetime Operation: Maintaining accuracy and consistency over extended periods. • Resource Constraints: Developing SLAM systems for devices with limited computational power. • Failure Recovery: Enabling systems to detect and correct mistakes without user intervention. • Prior Information: Using existing knowledge to improve mapping and localisation. continue

Here are some additional details regarding specific SLAM algorithms, their components, and practical considerations, as found in the sources: Key SLAM Components • Motion Model: Estimates the new pose of the robot, given the old pose and control or odometry commands. • Observation Model: Describes the likelihood of an observation, given the robot's pose and the map. • SLAM algorithms use these models to estimate the robot's trajectory and build a map of the environment. Kalman Filter-Based SLAM • Extended Kalman Filter (EKF): A commonly used approach that linearises non-linear functions using Jacobian matrices. • The robot's pose is included in the state vector. • Limitations: EKF-based SLAM can have computational issues with large-scale maps. Particle Filter-Based SLAM • Sample-Based Representation: Uses a set of samples (particles) to represent the probability distribution of the robot's state. • Proposal Distribution: Used to draw samples to advance the robot's state. • Correction and Weighting: Updates particle weights based on the difference between the proposal and target distributions. • Resampling: Focuses on high-probability areas by eliminating low-weight particles and duplicating high-weight particles. • FastSLAM: A particle filter approach where each particle maintains its own map. This allows for efficient computation, as the mapping process is independent for each particle. Graph-Based SLAM • Graph Optimisation: Modern systems use graph-based approaches, which reduce the sum of squared errors to optimise the map and trajectory. • Provides flexibility in terms of linearisation and relinearisation. Loop Closure Techniques • Loop Closing: Important for correcting drift and maintaining map accuracy when the robot revisits a known area. • Requires careful data association to avoid ambiguities, especially in symmetric environments. Practical Considerations • Real-world Applications: SLAM is used in various real-world applications, including autonomous navigation, transportation systems, and autonomous wheelchairs. • Online SLAM: A key property for real-world applications, where the map and pose are estimated in real-time rather than collecting all data beforehand. • Computational Constraints: SLAM algorithms must often operate under time and space constraints, especially in resource-limited systems. • Active SLAM: Robots make decisions on where to go to build better maps, as opposed to passive SLAM, where the robot follows a pre-defined path. Limitations and Open Issues • Dynamic Environments: Most SLAM algorithms assume a static environment, which is a significant limitation in real-world scenarios. • Failure Recovery: Systems often lack the ability to detect and correct mistakes without user intervention. • Prior Information: Exploiting prior knowledge about the environment is an area for improvement. • Multi-robot Systems: Integrating data from multiple robots can be tricky but has become more manageable with modern approaches. Additional Techniques and Considerations • Scan Matching: Used to align scans and improve pose estimates. • Homogeneous Coordinates: Used to represent transformations, especially with bearing-only sensors like cameras. • Data Association: The process of determining which observations correspond to which landmarks or features in the environment. • G Mapping: An open-source implementation of a grid-based SLAM system. • Frontends Help deal with ambiguities in the environment. put the icp portion as well

Here's what the sources say about Iterative Closest Point (ICP), including its function as a SLAM frontend: Core ICP Algorithm • ICP generally involves two steps: data association and transformation computation. • Data association typically uses a nearest neighbour approach to match points between two point clouds. This involves iterating over one point cloud and finding the closest point in the second point cloud. • Transformation computation then determines the transformation needed to minimise the distances between the corresponding points. This often involves computing the centres of mass of corresponding points and shifting the point clouds to align them, followed by computing the optimal rotation using a Singular Value Decomposition (SVD) based approach. • The process is repeated iteratively, recomputing data associations based on the improved alignment, until convergence is achieved. This involves repeatedly performing data association and alignment steps. ICP Variants and Enhancements • Point-to-plane ICP is a variant that assumes points originate from surfaces. Instead of minimising point-to-point distances, it minimises the distance between a point and the tangent plane of the closest point. This often yields better results. However, it typically requires moving away from an SVD-based approach to a general least squares approach, often solved using the Gauss-Newton method. • Generalised ICP combines point-to-point and point-to-plane metrics, also incorporating plane-to-plane metrics. It takes into account the local surfaces of point clouds, and is often a good first choice for scan registration. • Robust kernels can be integrated into error minimisation to reduce the influence of outliers. These techniques help to weigh down or ignore points that are wrongly aligned when computing the transformation. • Other techniques include projective ICP, which projects a model into a range image and aligns it. ICP in the Context of SLAM • ICP can serve as a SLAM frontend. • Limitations of ICP as a SLAM Frontend: ◦ ICP's sensitivity to the initial guess can lead to local minima, especially in symmetric or ambiguous environments. ◦ Inefficient sampling strategies for possible platform locations can also pose a challenge. • Ways to Improve ICP in SLAM: ◦ Arranging scans into maps instead of single scans. ◦ Separating local perceptions into parts, such as walls or obstacles. ◦ Using feature descriptors to find good estimates. • Ambiguity Management: Ambiguity can occur when places look similar. Global ambiguity refers to situations where the system can be in different places that do not intersect with the currently considered place. • Techniques for Addressing Ambiguity: One approach involves topological grouping of nearby poses and identifying consistent constraints within these groups. This involves testing for local unambiguousness and global sufficiency. Kiss ICP • Kiss ICP is a simple and effective system for light detection and ranging (LiDAR) odometry that uses a small number of parameters. • Key components of Kiss ICP: ◦ Motion prediction: Uses odometry, IMU data, or a constant velocity model to predict platform motion. ◦ Scan distortion correction: Corrects for motion during a scan. ◦ Spatial sub-sampling: Uses voxel grids or 3D hash tables to sub-sample point clouds. ◦ Correspondence search: Looks for neighbours in the map using the motion prediction to narrow the search. ◦ Least squares ICP: Runs ICP with a robust kernel for outlier rejection. create a set of questions and answers for an interviwe

Here are some potential interview questions and answers related to SLAM, based on the sources: Question 1: What is SLAM and why is it considered a "chicken or egg" problem? • Answer: SLAM stands for Simultaneous Localisation and Mapping. It is the process of estimating the trajectory of a robot or sensor and building a map of the environment at the same time. It's a "chicken or egg" problem because estimating the map is easier if the poses are known, and estimating the poses is easier if the map is known. Both quantities are unknown and must be estimated simultaneously, which makes the problem more complex. Question 2: What are the key components of a SLAM system? • Answer: The key components of a SLAM system include: ◦ A motion model that estimates the new pose of the robot given the old pose and control inputs or odometry commands. ◦ An observation model that describes the likelihood of an observation given the robot's pose and the map. ◦ A backend that optimises the map and trajectory based on the sensor data and models. ◦ A frontend which processes the sensor data and identifies features or landmarks, and determines the constraints between nodes. Question 3: Describe the Extended Kalman Filter (EKF) approach to SLAM. What are its limitations? • Answer: The Extended Kalman Filter (EKF) is a commonly used approach to SLAM that uses the Kalman filter framework to estimate the robot's state recursively. It involves a prediction step, where the next state is predicted based on the previous state and control inputs, and a correction step, where the prediction is corrected based on new sensor observations. Because the models are non-linear the EKF uses Jacobian matrices to linearise the functions. • Limitations of EKF-based SLAM are that it can have computational issues with large-scale maps. Question 4: How do particle filters work, and how can they be applied to the SLAM problem? • Answer: Particle filters use a sample-based representation to approximate probability distributions with a set of samples, or particles. These filters draw samples from a proposal distribution to advance to the next state. The particle weights are adjusted to account for the difference between the proposal and target distributions. Resampling eliminates particles with low weights and duplicates those with high weights to focus on high-probability areas. • In SLAM, particle filters, like FastSLAM, split up the estimate about the trajectory of the robot from the map of the environment in order to perform state estimation efficiently. Question 5: What is loop closure and why is it important in SLAM? • Answer: Loop closure occurs when the robot revisits a known area after a long traversal. It's important for correcting drift and maintaining map accuracy. Loop closure requires careful data association to avoid ambiguities, especially in symmetric environments. Question 6: What is the role of a front end in SLAM? Describe one approach to managing ambiguities in SLAM. • Answer: A SLAM front end is used to determine if a constraint is likely to be correct, helping to manage ambiguities in the environment. • One approach to managing ambiguities involves performing topological grouping of nearby poses and identifying consistent constraints within these groups. This includes testing for local unambiguousness and global sufficiency. • Local unambiguousness ensures that there are no overlapping matches that could lead to a "picket fence" problem. • Global sufficiency ensures that there is no possible disjoint match in the uncertainty ellipse. Question 7: What is ICP and how can it be used as a SLAM front end? What are its limitations and how can they be improved? • Answer: ICP (Iterative Closest Point) is an algorithm used to minimise the difference between two point clouds. It can be used as a SLAM front end by iteratively aligning scans to find loop closures. The two primary steps are data association and transformation computation. • Limitations of ICP include its sensitivity to the initial guess and inefficient sampling strategies. • Ways to improve ICP in SLAM include arranging scans into maps instead of single scans, separating local perceptions into parts, and using feature descriptors to find good estimates. Question 8: What are some of the limitations and open issues in SLAM? • Answer: Some limitations and open issues in SLAM include: ◦ The assumption of static environments, which is a significant limitation in real-world scenarios. ◦ The lack of ability to detect and correct mistakes without user intervention. ◦ The challenge of exploiting prior knowledge about the environment. Question 9: Explain the difference between full SLAM and online SLAM. • Answer: ◦ Full SLAM involves estimating the entire trajectory of the robot and the map of the environment. ◦ Online SLAM only estimates the current pose of the robot and the map built up to the current point in time. Online SLAM is crucial for robots making real-time decisions based on their current location and surroundings. continue

Here are more potential interview questions and answers related to SLAM, based on the sources: Question 10: What is the difference between a motion model and an observation model in SLAM? • Answer: ◦ A motion model describes how the robot moves through its environment. It estimates the new pose of the robot, given its previous pose and control inputs such as odometry commands. ◦ An observation model describes how the robot perceives its environment through its sensors. It provides the likelihood of an observation, given the robot's pose and the map of the environment. It relates what the robot is expected to measure based on its location. Question 11: Can you explain the concepts of 'passive SLAM' versus 'active SLAM'? • Answer: ◦ Passive SLAM deals with incoming data streams from sensors without the robot making decisions about where to go. The robot is driven, perhaps with a joystick, and the SLAM algorithm processes the data. ◦ Active SLAM, on the other hand, involves the robot making its own decisions about where to move in order to build a better map of the environment. This includes exploration and deciding where to go to improve the map. Question 12: What are some key ingredients of Kiss ICP? • Answer: Kiss ICP is a LiDAR odometry system with a small number of parameters. Key ingredients include: ◦ Motion prediction using wheel encoders, an IMU, or a constant velocity model. ◦ Scan distortion correction to account for robot motion during a scan. ◦ Spatial sub-sampling using voxel grids or 3D hash tables. ◦ Correspondence search using motion prediction to improve data association. ◦ Least squares ICP with a robust kernel for outlier rejection. Question 13: How does the point-to-plane ICP algorithm differ from the standard point-to-point ICP? • Answer: The point-to-plane ICP algorithm differs from point-to-point ICP by taking into account that the objects being scanned are surfaces. Instead of minimising the Euclidean distance between points, it minimises the distance between a point and the estimated tangent plane of the closest point on the other surface. This typically leads to better convergence with fewer iterations. Question 14: What is the purpose of homogeneous coordinates? • Answer: Homogeneous coordinates are useful when working with sensors that only measure the direction to obstacles, not the distance. An example of this is a camera. A camera projects a 3D world onto a 2D image plane. Question 15: In the context of graph-based SLAM, what are some advantages of graph-based approaches? • Answer: Graph-based approaches are popular because of their flexibility in terms of linearisation and relinearisation. The graph-based framework is motivated by reducing the sum of squared errors, which is equivalent to finding the mode of a Gaussian distribution.