Research Trends in
Autonomous Space-Based
Planning and Scheduling
5th International Workshop on Planning
and Scheduling for Space
Gina Moylan
Department of Aerospace Engineering
University of Maryland, SSL
gmoylan @ssl.umd.edu
Ella M. Atkins
Department of Aerospace Engineering
University of Michigan
[email protected]
Introduction
• Many examples of ground-based
automation—e.g., SPIKE, AMPS
support for ST5 Constellation, etc.
• However, there are currently only two
examples of on-board satellite
autonomy: ASE and PROBA
• Concerned with reasons for limited
proliferation
Page 2 -- 10/3/2015
Significant Challenges
• Immediate answer: Automation in this domain is
difficult…
– The dearth of hardware and software standardization
– Extensive time frames associated with the design,
construction and implementation of space systems
– Economic and practical difficulties of launch
– Complexity of spacecraft
– Harshness of the operating environment(s)
– Limited on-board resources and communication
opportunities
– Implementing dynamic real-time response systems
– Political and fiscal challenges, etc.
Page 3 -- 10/3/2015
Outline
– Review flight-proven space-based planning
and scheduling applications
– Review some applicable frameworks and
architectures
– Discuss limitations
– Application focus: space-based self-assembly
– Common research trends/recommendations
Page 4 -- 10/3/2015
Flight-proven Architectures
Page 5 -- 10/3/2015
Clementine Deep Space Probe
Science Experiment (DSPSE)
• First application of on-board
autonomous spacecraft
scheduling operations
(1994)
• Executed commands via
rules-based SCL script
• Automation triggered by
receipt of ground state
vectors during routine orbit
Clementine or Deep Space Probe
Science Experiment (DSPSE)
Page 6 -- 10/3/2015
Remote Agent Experiment, DS-1
• First flight-proven
integrated example of
closed-loop P&S for
satellite operations (1999)
(Deep Space-1)
– Three-tiered architecture
– PS used a high-level declarative modeling
language with depth-first search—limited
backtracking with heuristic support (PS
response time max ~ 4hrs)
– Exec uses plan runner to check constraint
satisfaction before executing planned
commands
– MIR layer provides interface between exec
and controllers with Mode Identification (MI)
and Mode Recovery (MR)
– Used Batch commands to control s/c
Page 7 -- 10/3/2015
Autonomous Sciencecraft
Experiment, EO-1
• First continuous application of
integrated P&S (2004)
– Uses iterative repair based on
the methods available given a
set of constraints (Planner
response time ~10s min)
– Tight coupling between
CASPER and s/c constraint
models and science data
analysis
– Redundancy built in each layer
for functionality and safety
– Uses heuristics and fixed values
for temporal offsets—reduces
search space
EO-1 satellite
Page 8 -- 10/3/2015
The Project for On Board
Autonomy, PROBA
• Operates with limited intervention
from the ground
• Performing onboard everyday
tasks e.g., guidance, navigation,
control, onboard scheduling and
payload resource management
• Does not handle spacecraft
anomalies autonomously
• Does not use extensive modeling
PROBA satellite
Page 9 -- 10/3/2015
Other Architectures and
Frameworks
Page 10 -- 10/3/2015
Intelligent Distributed Execution
Architecture, IDEA
• Distributed temporal planner
• Procedures are tokens
• Agent parameters specified
by central database model
control token exchange and
execution
• Implements sense-plan-act
loop as a virtual machine
within a communication
wrapper with reactive-based
real-time guarantees
(Muscettola et al. 2002)
Page 11 -- 10/3/2015
The Coupled Layer Architecture for
Robotic Autonomy (CLARAty)
• Two-tiered architecture
• Tightly couples the
planner and executive
into one decision layer
that interacts with a
functional layer at all
levels of the system
• Common representation
for planner and exec
(Volpe et al., 2001)
Page 12 -- 10/3/2015
Closed-Loop Execution and
Recovery (CLEaR)
• Combination of architecture
and framework approaches
– CLARAty framework
– ASE’s CASPER Planner
– Plan runner to transfer
activities to Task Description
Language (TDL) executive
• Heuristic support
determines whether
conflicts should be handled
by the planner or executive
(Estlin et al. 2002)
Page 13 -- 10/3/2015
IXTET-EXEC
• Uses lifted partial order temporal planning based on
CSPs
• Temporal executive interacts with planner and controls
temporal network
• Flexible plans—allows conditional plan repair interleaved
with plan execution
• Plan repair uses non linear planning techniques
under certain assumptions
• Interleaving partial order planning and execution may
insert flaws in the plan—planning process is not
guaranteed to find a valid plan for all execution failures
• Formal definitions for conditions of partial-plan execution
• Requires temporal/resource flexibility to be very effective
(Lemai and Ingrand 2005)
Page 14 -- 10/3/2015
Common Qualities
A
S
E
R
A
PROBA
I
D
E
A
CLARAty
Flight-Tested
•
•
•
Hardware-Tested
•
•
•
Continuous Planning
Anomaly resolution
•
•
•
•
•
•
•
•
•
•
•
Plan repair during
execution
Scales with multiple
agents
Common
representation
Flexible timing
IXTET-EXEC
•
•
•
•
•
•
Full navigation &
guidance
Page 15 -- 10/3/2015
Limitations
• A disconnect between philosophies and
implementations in planning and executing
action
• Limited hardware and software standardization
makes validation at all system levels prohibitive
• More research in the area of autonomous
navigation and guidance capabilities is
needed to implement applications involving
multiple spacecraft
Page 16 -- 10/3/2015
Autonomous Navigation/Guidance
Focus Application
Page 17 -- 10/3/2015
Self-Assembly
• Motivation:
– For a 10km x 2km SSPS (Space Solar Power Satellite)
> 2,500 hours of astronaut space walk
> $3 billion for assembly cost
•
Types of structures and applications:
– Very Large Solar Power Array
– Large Orbital Reflector Telescope
– Lunar base modules
– Satellite constellations
– Component repair
– Nano-satellite swarms
(Wei-Min Shen
et al.)
Page 18 -- 10/3/2015
Action Choices are Motion
• Problems must integrate physics-based
reasoning system trajectories and
deliberative capabilities in a very cohesive
way
• Action choices for each component and
corresponding trajectories scale with the
number of assembly members
• Difficult to coordinate the dynamics of
these systems in terms of motion and
assembly/functional choices
• Resource optimization requires fullstate trajectories—i.e., geometric
motions (paths) that include point
velocities/accelerations governed by
nonlinear differential equations of
motion
Page 19 -- 10/3/2015
Translating Action and Motion
• Atkins, Moylan and Hoskins,
Space-Based Assembly with
Symbolic and Continuous
Planning Experts, IEEE
Aerospace, 2006
• PDDL/Uniform Cost Search
Engine in C++: SSLTaskMaster
• Translator interfaces with search
engine and astrodynamics experts
– Orbital Insertion Expert: Lambert’s
Solution
– Proximity Operations Expert:
Clohessy-Wiltshire (Hill's) equations
Task
P lan n er
K no w led ge
B a se (P D DL )
a c n , p a rn ,  k z k , 0 n
J [ ],  k z k , f 
Tran slator
Fu n ction

D yn a mics,
O bsta cle s,
C o st Fu n ction
b2

z b 1 f ,  k z k , 0 
z b 1 ( t ), J [ ],  k z k , f
A strod yn am ics
P lan n in g
E xp erts
Page 20 -- 10/3/2015

PDDL Example
(define
(domain blocks-in-space)
(:requirements :equality)
(:predicates
(block ?b)
(orbit ?o)
(target-orbit ?to)
(face ?f)
(in-orbit ?b ?o)
(clear ?b ?f)
(docked ?b1 ?f1 ?b2 ?f2)
(assembled ?b)
(free ?b))
(:action insert
;
;
;
;
;
;
;
;
;
;
?b is a block
?o is an orbit
?to is the target orbit where assembly takes place
?f is a block face
block ?b is in orbit ?o
face ?f of block ?b is clear (undocked)
face ?f1 of block ?b1 is docked to face ?f2 of block ?b2
block ?b is part of the assembled structure
block ?b is free to move, not assembled--all faces are clear
insert block ?b residing in orbit ?o1 into orbit ?o2
:parameters
:precondition
(?block-1 ?orbit-1 ?orbit-2)
(and (block ?block-1)(free ?block-1)(orbit ?orbit-1)(orbit ?orbit-2)
(target-orbit ?orbit-2)(in-orbit ?block-1 ?orbit-1))
:effect
(and (in-orbit ?block-1 ?orbit-2)(not (in-orbit ?block-1 ?orbit-1))))
(:action dock
; move free ?b1 so that its face ?f1 docks to face ?f2 of ?b2
:parameters
(?block-1 ?face-1 ?block-2 ?face-2 ?orbit-2)
:precondition (and (block ?block-1)(block ?block-2)(face ?face-1)(face ?face-2)(free ?block-1)
(clear ?block-2 ?face-2)(target-orbit ?orbit-2)(in-orbit ?block-1 ?orbit-2)
(assembled ?block-2))
:effect
(and (docked ?block-1 ?face-1 ?block-2 ?face-2)(assembled ?block-1)(not
(clear ?block-1 ?face-1))(not (clear ?block-2 ?face-2))(not (free ?block-1))))
(define (problem assemble-four-blocks)
(:domain blocks-in-space)
(:objects
block-a block-b block-c block-d orbit-a orbit-b orbit-c orbit-d face-pos_y face-neg_y)
(:init
(block block-a)(block block-b)(block block-c)(block block-d)(orbit orbit-a)
(orbit orbit-b)(orbit orbit-c)(orbit orbit-d)(face face-neg_y)(face face-pos_y)
(target-orbit orbit-a)(in-orbit block-a orbit-a)(in-orbit block-b orbit-b)
(in-orbit block-c orbit-c)(in-orbit block-d orbit-d)(clear block-a face-pos_y)
(clear block-a face-neg_y)(clear block-b face-pos_y)(clear block-b face-neg_y)
(clear block-c face-pos_y)(clear block-c face-neg_y) (clear block-d face-pos_y)
(clear block-d face-neg_y)(assembled block-a)(free block-b)(free block-c)(free block-d))
(:goal
(and (assembled block-a)(assembled block-b)(assembled block-c)(assembled block-d))))
Page 21 -- 10/3/2015
Future Work
• Future focus on unifying common
approaches and aspects by distance and
orbital parameters
Selected statistics of self-assembly runs
Number of
blocks
Total
Assembly
Cost (dv)
Time to
Goal log(s)
Number of
Possible
Actions
4
72.2787
0
320
6
75.8849
0.477121
1080
8
106.429
0.903089
2560
9
116.949
1.04139
3645
27
477.972
4.337339
98415
Initial
Deployment
Exploded
view
Page 22 -- 10/3/2015
Research Trends and
Recommendations
Page 23 -- 10/3/2015
Trends
• Unify the planning and execution processes
under the same database and
language/representation, making the executive
and planner aware of the same constraints
• Incorporate flexible time execution
• Enable procedural capabilities during plan
generation and repair
• Use modular system modeling—e.g., object
oriented approaches—to aid in system validation
Page 24 -- 10/3/2015
Recommendations
• Design fault protection at every layer for redundancy
• Develop planning systems to interact with legacy control software
and established spacecraft models
• Design planning and executive systems to coordinate with other
software to evaluate whether a science operation was successful—
science goals drive remote exploration and therefore should be a
top priority
• Allow spacecraft experts to encode models themselves with tools
and languages already familiar to them
• Design software to be flexible when state information is uncertain—
this is especially important in ground-based missions
• Incorporate path planners that search for paths based on different
constraints, e.g., shadows, communication, timing, terrain, etc.
• Focus on plan repair when things go wrong and when things go
better than expected.
Page 25 -- 10/3/2015
Conclusions
• Many important advances in space-based
planning and scheduling
• Despite advances, more unification is needed,
particularly in the areas of coupling planners and
executives with flexible temporal response
• More research is needed to integrate the areas
of symbolic and physics-based reasoning for
planning actions and executing them
Page 26 -- 10/3/2015
Darn, That’s the End…
Thank you!
PS. My commentator promised to be nice to
this graduate student! ;-)
Page 27 -- 10/3/2015
Descargar

Complexity results for standard benchmark domains in