Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

Path planning for autonomous local navigation of a planetary exploration rover

Mars Missions

Exploration to gain insight on the Red Planet's past

Mars Missions

Curiosity and Perseverance

2012

Mars Science Laboratory

Sojourner

1997

Mars Pathfinder Mission

2020

"Percy" and Ingenuity

1960s / 1970s

Many unsuccessful Fly-by attempts

until

US Mariner 4 , 6 , 7

History

US Mariner 9

URSS Mars 2 (1971)

Viking 1, 2 (1976)

Spirit and Opportunity

2004

Mars Exploration Rovers

(MER-A and MER-B)

Challenging Daily Operations

Rover Activities

-Latency

-Line of Sight

-Resource Management

High Level of Autonomy Desired

-Navigation

-Data gathering

-Uplink and Downlink Cycles

Autonomous Navigation System

Hazard Detection and Avoidance

using

On-board Sensing, Perception and Planning

Autonav System

Capability to perceive the nearby terrain and move accordingly on its own

Drive Modes

Blind Drive (Directed Driving)

-Simplest Drive Mode

-No Visual Sensing

-Highest Speed (120 m/h)

-Used on Flat (and possibly already explored) Surfaces

Drive Modes

AutoNav

-Slowest Drive Mode

-Geometric Analysis of the Terrain

-Used in Hazardous and Unknown Environment

Traversability ("Goodness") Map

Terrain Analysis through Stereo Vision Cameras and Image Processing

"Cloud" of 3D Points representing the Terrain, used to build a Grid-based Map

Traversability Map

Each Grid Cell is Evaluated

High values-easily traversable terrain

Low values-hazardous area

Set of Arcs Generated and Best Path Evaluated (i.e. through Algorithms)

Simulation Environment

ROS - Robot Operating System

Middleware Suite-Collection of software frameworks

Simulation Environment

Gazebo Simulator

-Open-Source Simulator

-Physics engine, rendering, support code for sensor simulation and actuator control.

Gazebo and Rviz

Rviz

-Graphical interface

-3D visualization

-Display data from camera, lasers,devices

“RVIZ shows you what the robot thinks it’s happening, while Gazebo shows you what is really happening.”

-Morgan Quigley

Curiosity 3D Model

17 "Camera Eyes"

-Engineering Cameras

-Science Cameras

-Descent Imaging Cameras

Created by the NASA Visualization Technology Applications and Development (VTAD) department

Rover Model

6 wheel drive and suspension, arm control and mast movement, cameras to create video based navigation

-Hazard Avoidance Cameras (Hazcams)

-Navigation Cameras (Navcams)

Mars Gazebo World

Gazebo World Map

Based on Real Martial Holography and DEMs (Digital Elevation Models)

Martian gravity and physics enabled

Mars Environment

Planning Implementation

First Steps and Bug2 Build

Ros Package

First Test Build

Planning Implementation and builds

-Installing Ros and Gazebo (sudo apt get command)

-Checking Dependencies

-Source Environment

Bug2 Algorithm -based Navigation

-Ros Navigation Stack

Create a Catkin_ws (catkin_make command)

-Source Space

-Build Space

-Development Space

-Subfolders

Add LIDAR Sensor through the mobile_manipulator command

Create/Edit .py script file(src)

-Define variables, callbacks and states

-Create .launch file

Adding .world file in src and create .launch file

Copy in a "models" folder (cp command)

Create .config and .sdf files for the Model and edit

Open Gazebo and "Insert" model in world

Simplified Rover Model

Wheel Positioning Test

Download and Open in Sketch up:

-Metric measurements, Export 3D model

-.dae files for Mass and Collision

Navigation Map Cells

Regular Grid

3D Model for Simulations, freely available on Nasa's Website

Rviz Plugin: GridMap

Mobile_Manipulator to edit Camera Sensors

Rover Model

Navigation logic

BFS expands each state in the navigation map with the highest score of reaching the selected goal position.

The score of a developed state is calculated using a heuristic evaluation function :

Configure the ROS Navigation Stack to perform planning

-mkdir param command

-configure costmaps in .yaml files

-mobile_manipulator/param and add mobile_manupulator.rviz

Move_Base ROS Package

A* Algorithm

A* planner Build

Edit Base_local_planner script file- Dijkstra's Algorithm

Edit Costmaps (Replace .yaml files)

Traversability cost function-chosen as the sum of the terrain difficulty measure and the distance to travel

2 Data Structures : OPEN & CLOSED list

- OPEN list keeps track of the states that are considered for expansion and its implemented through priority queue

- CLOSED list contains states that A* has already expanded and thus have been removed from the OPEN list.

Wnavi , Wnavj belong in [0, 1] and Wnavi + Wnavj = 1

Guided Path Planning Cost Function

Heading Cost Function

• The g-value g(s) represents the cost of the optimal path found so far to reach state s

• The h-value h(s) is the estimation of the goal distance

• The f-value f(s) is the key, calculated for each state, estimation of the total cost of travel from start to goal through state s

P-Primitive BFS-Best First Search

-the sub-goal cell has to lie on the border of a navigable region continuously connected to the rover location

-the distance between the sub-goal location and the imaginary line connecting the rover and the target should be minimized

-the selected sub-goal position is validated if a greedy best first is

able find a path from the rover position.

A* loop - In each iteration it extracts from the OPEN list the state s with the lowest f-value, checks where neighboring state s' is stored in the lists and updates it accordingly by setting the g-value of state s’ to the

g-value of state s plus the cost of traversing from s to s’ and assigning the parent of s’ to state s.

Drawbacks:

-In place turns

-Space complexity, as it stores all generated nodes in memory.

Control set Planning

Non-holonomic Motion Planning

Fixed resolution grid decomposition of the environment-control set for the origin generated.

For a given grid position- control set generated considering length and radius of the curved paths, discretized headings and branching factor.

Regularity property : all the control set generated at the origin can be reproduced at any other position in the grid

Main objective: generate paths which incorporate the steering capabilities of the rover

[Barraquand and Latombe, 1991]:

Integrating the kinematic model of the rover to generate motion primitives. Planner iteratively builds a search tree which keeps track of all reachable configurations up to a depth of H arcs.

NumberArcs-cardinality of outgoing paths from each state(branching factor)

ArcLenght-final position of straight path

CalculateMotionPrimitive-finds the closest discrete state to the

provided final configuration and calculate a motion primitive between the origin and the discrete state

Discretized version of the BL planner:

The state lattice encodes the motion capabilities of the robotic system, allows to represent the entire navigation space of the rover as a compact set of motion controls localized at any reachable position

Stopping Conditions:

Latest state from the OPEN list lies in a neighborhood of the goal state-planner returns path to goal state

Exploration Depth Parameter-size of the search tree is bounded-solution is guaranteed to be given in a finite amount of time

3D states (x, y, theta)-results in exponential growth in complexity as the dimension of the search space increases-A* adapted to include heading value, when more than one motion primitives reach the same grid cell with the same heading, only the lower cost path is retained

• Minimum turning radius: smallest radius of a circular path that the rover can follow

• Branching factor: Number of motion controls leaving from a given state.

• Translational discretization: The resolution of the grid representing the navigation space environment.

• Heading discretization: The resolution of the heading direction of the rover.

• Primitive length: The distance the rover would drive on a given path primitive (straight line or arc).

Cost Function:

Non-holonomic Planner Build

sbpl_lattice_planner

In-place Maneuvers

In-place-turn maneuvers - very expensive in time and energy: The rover has to stop the locomotion, reorient the wheels, perform in-place turn continue the execution of the planned path

Planner plugin for move_base and wraps the state lattice search-based planning library.

Paths are generated by combining a series of motion primitives, planning is done in x, y, and theta dimensions, resulting in smooth paths that take robot orientation into account.

In this situation, both rover security

and trajectory execution time are improved after one in-place turn

Set "base_local_planner" parameter to "SBPLLatticePlanner"

Edit to set parameters and/or motion primitives:

~/SBPLLatticePlanner/allocated_time

~/SBPLLatticePlanner/initial_epsilon

~/SBPLLatticePlanner/genmprim_unicycle.m - forward, backward, turn-in-place, forward-turn-arcs

Turn Policy

-In-place-turn is commanded only when the target is behind the rover

-The heading change of the rover ThetaR is commanded to reach the value of the angle ThetaP given by the path primitive

Simulation Results

-Set of Experiments

-150 Comparative Simulations for Each Approach

-Random Configurations, Same starting Point

Simulation Results

-A* grid planner-success rate of almost 100%

-Smaller the branching factor, lower the success rate

-Time improvement rate shows the cases where the nonholonomic path planner outperforms the A* grid planner

-Higher branching factors result in much slower computation time

- Nonholonomic path planner provides paths easier to navigate

-Paths calculated using motion control sets are longer than the ones provided by the grid based A* planner

-Increasing the branching factor results in shorter paths

In-Place Turns

In-place Turns

-A* grid path planner caused the highest total number of in-place-turn maneuvers,

at least 1 in-place rotation for at least 75% of the mission test cases

-Nonholonomic motion planner reduces the number of in-place turns of 40%, and 38% of the mission targets are reached with no inplace-turn maneuvers

-In-place turn paths :4% longer than the ones provided by the A* grid planner

-Cases without in-place turns : paths 55% longer

Time Comparison

Total simulation time to reach a given mission goal:

-Taking perceptions

-Navigation map building

-Path planning and path execution

-Nonholonomic path planner has lower computation time than the A* grid path planner in 62% of the mission scenarios

Time and Memory

Memory Comparison

-Nonholonomic path planning using a branching factor of 5 has a much less memory use than when using a branching factor of 7

-A* grid planner has a much high memory use

Learn more about creating dynamic, engaging presentations with Prezi