heather2

Spacecraft Rendezvous and Docking with Real-Time, Randomized Optimization: 

Spacecraft Rendezvous and Docking with Real-Time, Randomized Optimization Phillips, Kavraki, and Bedrossian, 2003 Presented by Heather Arneson September 19, 20006

Overview: 

Overview Base Problem: 6 degree-of-freedom spacecraft rendezvous and docking problem Impulsive control Avoidance of known obstacles Avoidance of plume impingement Minimize fuel use Extension of Base Problem: Real-time obstacle avoidance

Plume Impingement: 

Plume Impingement

Method: 

Method Hybrid offline-online technique Offline Probabilistic search is used to generate a path that avoids collision and plume impingement Online Gradient descent method used for real-time obstacle avoidance Feedback control loop to handle error in the initial offline solution

Inputs to Algorithm: 

Inputs to Algorithm Start and goal configurations of chase vehicle relative to target vehicle Method to check for collisions and violation of other constraints Method to integrate impulsive control Metric to determine cost for a given control Estimate of cost from a particular configuration to the goal configuration

Algorithm 1:Randomized Tree Expansion: 

Algorithm 1: Randomized Tree Expansion for i = 0 to N do p = CHOOSE_WAYPOINT() n = EXPAND_WAYPOINT(p) ADD_TO_TREE(p,n) end for

CHOOSE_WAYPOINT(which waypoint should be expanded?): 

CHOOSE_WAYPOINT (which waypoint should be expanded?) Compute weight for each waypoint weight(p) = order(p)/(A*_cost(p) out_degree(p)) out_degree(p) = # times p has been expanded order(p) => more recent nodes chosen more often Randomly select waypoint with probability proportional to it’s weight => Not just following the locally optimal direction => won’t get stuck in local minima

EXPAND_WAYPOINT: 

EXPAND_WAYPOINT Creates a new waypoint, n, p -> n is likely feasible Apply a control to p and integrate to get n Control direction, magnitude, time to integrate chosen at random Cost computed easily Only feasible movements from a waypoint are considered and explored (no collision check)

ADD_TO_TREE: 

ADD_TO_TREE p -> n feasible? (check for collision) cost(n) = cost(p) + cost(p -> n) n is added as an outbranch from p estimate cost(n -> goal) n -> goal feasible? (check for collision) (how do they know how to get from n to goal?) cost to goal through n is calculated store lowest cost path

Range Searching: 

Range Searching Include proximity of waypoint to other waypoints in the weight to expand search at the perimeter of explored space What is close when using kinodynamic constraints?

Path Gradient Descentbest path refinement (offline): 

Path Gradient Descent best path refinement (offline) Find the cost gradient of the path and incrementally perturb the path in that direction Perturb each waypoint in the path in the direction of the gradient of that waypoint Deform waypoints to decrease cost while not violating constraints

Algorithm 2:Path Gradient Descent: 

Algorithm 2: Path Gradient Descent for i = 0 to N do randomly permute order of waypoint considered for j = 0 to # waypoints do calculate gradient follow gradient e end for end for

Dynamic Obstacle Avoidance(online): 

Dynamic Obstacle Avoidance (online) Path Gradient Descent technique can be extended to work in a changing environment Can be used as feedback control Account for integration error Dynamic obstacle avoidance

Guided Randomized Expansion Tree: 

Guided Randomized Expansion Tree

A Low Cost Path: 

A Low Cost Path

Path Gradient Descent: 

Path Gradient Descent Initial Path Refined Path

Dynamic Obstacle Avoidance: 

Dynamic Obstacle Avoidance Avoidance Paths Initial Path Final Path