Motion planning algorithms

motion planning for humanoid robots and plan in motion meaning
Dr.AldenCutts Profile Pic
Dr.AldenCutts,United Kingdom,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Comment
Path/Motion Planning: An overview Jonas Kvarnström Automated Planning and Diagnosis Group Department of Computer and Information Science Linköping University jonas.kvarnstromliu.se – 20172 2 Path/Motion Planning (1)  Perhaps the easiest form of path planning / motion planning:  (1) A robot should move in two dimensions between start and goal ▪ Avoiding known obstacles – or it would be too easy… Start position Goal position jonkvi jonkvida da3 3 Path/Motion Planning (2)  Perhaps the easiest form of path planning / motion planning:  (2) The robot is holonomic ▪ Informally: Can move in any direction (possibly by first rotating, then moving) jonkvi jonkvida da4 4 Path/Motion Planning (3)  Problem: Generating an optimal continuous path is hard  Common solution: Divide and conquer ▪ Discretize: Choose a finite number of potential waypoints in the map ▪ Assume there exists a robot-specific local planner to determine whether one can move between two such waypoints (and how) ▪ Use search algorithms to decide which waypoints to use Start position Goal position Remaining task: choosing potential waypoints + finding a path using them jonkvi jonkvida da6 6 Regular 2D Grid  The simplest type of discretization: A regular grid  A robot moves only north, east, south or west ▪ Details are left to the local planner Start position Goal position jonkvi jonkvida da7 7 Regular 2D Grid: Real Obstacles Partially covered – can’t be used  Real obstacles do not correspond Obstacle to square / rectangular cells…  But we can cover them with cells Start position Goal position jonkvi jonkvida da8 8 Regular 2D Grid: Discrete Graph  View the grid implicitly as a discrete graph  Assume the local path planner can take us between any neighboring cells ▪ Between blue nodes ▪ No obstacles in the way ▪ Sufficient free space to deal with non-holonomic constraints jonkvi jonkvida da9 9 Regular 2D Grid: Discrete Graph (2)  Connect start/goal configurations to the nodes in their cells  Within a cell  no obstacles  can plan a path using local planner  Here, the goal is unreachable… jonkvi jonkvida da10 10 Regular 2D Grid: Grid Density  Grid density matters  Here: 4 times as many grid cells  Better approximation of the true obstacles, but many more nodes to search jonkvi jonkvida da11 11 Non-Regular Grids  Alternative: Use non-regular grids  For example, denser around obstacles  (Or even non-rectangular cells) jonkvi jonkvida da12 12 Grid Representations  Space-efficient data structure: quadtree  Each node keeps track of: ▪ Whether it is completely covered, partially covered or non-covered  Each non-leaf node has exactly four children jonkvi jonkvida da13 13 Grid Representations  Can be generalized to 3D (octree), … jonkvi jonkvida da15 15 Regular 2D Grid: Grid Density  Grid-based methods can result in many nodes  Even with efficient representation, searching the graph takes time  Alternative idea: Place nodes depending on obstacles  Simple case: Known road map  Model all non-road areas as obstacles, then add a dense grid?  Or place a node in each intersection? jonkvi jonkvida da16 16 Visibility Graphs  Visibility graphs  Applicable to simple polygons ▪ Nodes at all polygon corners ▪ Edges wherever a pair of nodes can be connected using the local planner  Mainly interesting in 2D ▪ Optimal in 2D, not in 3D q qoal q init jonkvi jonkvida da17 17 Voronoi Diagrams  Voronoi diagrams  Find all points that have the same distance to two or more obstacles ▪ Maximizes clearance (free distance to the nearest obstacle)  Creates unnecessary detours  Mainly interesting in 2D – does not scale well jonkvi jonkvida da19 19 Introduction  So far, we implicitly assumed:  If we can draw a line between two waypoints, We need to introduce the robot can move between the waypoints some new concepts…  But: How does an airplane fly this path? jonkvi jonkvida da20 20 Work Space  A car moves in a 2-dimensional plane  The workspace of the car  Many robots have a 3-dimensional workspace jonkvi jonkvida da

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.