On the Design of Symbolic-Geometric

Online Planning SystemsLavindra de Silva - University of Nottingham

Felipe Meneguzzi - PUCRS

O Brasão da Universidade é composto por cinco cores:

AZULNa faixa em dois tons desta cor, sobre a qual se lê a expressão

em latim AD VERUM DUCIT (Conduz à verdade).

OURONa chave à esquerda de quem olha, na altura da tiara papal

(coroa no alto), na estrela de sete pontas e no M que representa

Maria e a Congregação Marista.

PRATANa chave à direita e na tiara papal (coroa no alto).

PRETONas pequenas mosquetas em forma de cruz sobre o fundo

branco do Brasão.

VERMELHONa cruz invertida de São Pedro chamada “Tau” e nas faixas

pendentes da tiara papal.

Pantone Process

CMYK

RGB

Pantone Process

CMYK

RGB

Pantone Process

CMYK

RGB

Pantone Process

CMYK

RGB

100C 60M 0Y 0K

100C 60M 0Y 20K

0R 102G 179B

0R 84G 150B

293C

Pantone Process

CMYK

RGB

0C 0M 0Y 100K

0R 0G 0B

Black C

294C

5C 25M 55Y 20K

197R 160G 108B

871C ou 465C

0C 0M 0Y 25K

198R 200G 202B

877C ou 421C

Pantone Process

CMYK

RGB

0C 100M 95Y 30K

177R 16G 26B

1807C

ELEMENTOS GRÁFICOSBRASÃO - ESCALA DE CORES

9MANUAL DE IDENTIDADE PUCRS

Motivation• Programming autonomous robots is hard

• Wide variety of algorithms

• Varying granularities for data and decision-making

• Implementations often combine symbolic (high-level) and geometric (low-level) reasoning

• Recent work on integrating symbolic and geometric planning

2

Background

"Classical" Planning• Classical Planning: Discrete states (logic formulas) + atomic actions

• Problems are defined in terms of a domain, an initial state and

• STRIPS/PDDL — declarative goal state

• HTN — procedural desired task

• HGN — hybrid between STRIPS/HTN

• Solution is a sequence of discrete actions

4

Geometric Planning• At the lowest level, involves motion planning

• 3D perception, search in continuous high-dimensional space

• May include preferences and other high-level reasoning

• Environment comprises a 3D world with polygonal obstacles

• Solution is a collision-free sequence of poses

5

BDI Logic• Originally proposed by Rao and Georgeff, later formalised in the AgentSpeak(L)

language, assumes an agent

• Behaviour defined in terms of plan rules triggering_event : context <- body.

• where:

•the triggering event denotes the events that the plan is meant to handle;

•the context represent the circumstances in which the plan can be used;

•the body is the course of action to be used to handle the event if the context is believed true at the time a plan is being chosen to handle the event.

Ag = hEv ,Bel ,PLib, Inti

6

Desiderata

Deliberation

Symbolic Planning/Execution

Geometric Planning/Execution

Action Perception

Robotic Devices

Monitoring

Anchor Filtering

Abstract Architecture

• Robot behaviour implementation is often decomposed at various levels of abstraction

• We envision a tiered architecture incorporating advances

8

Desiderata - Symbolic Level• Deliberation: Centered around declarative goals

• Selecting relevant goals - a.k.a. desire selection

• Filtering for achievable goals - a.k.a. intention selection

• Deciding when to give up - a.k.a. commitment strategy

• Symbolic Planning and Execution

• Decomposes goals from deliberation into discrete tasks and actions

• Contains an abstracted representation of geometric models

Deliberation

Symbolic Planning/Execution

Geometric Planning/Execution

Action Perception

Robotic Devices

Monitoring

Anchor Filtering

9

Desiderata - Anchor Filtering• Infeasible to replicate full 3D models at the

symbolic level (even if discretised):

• Explosion in the number of symbols

• Inefficiency in logic queries

• Rather, we propose to selectively keep anchors between symbolic and geometric level

• Could be predefined or computed at runtime

Deliberation

Symbolic Planning/Execution

Geometric Planning/Execution

Action Perception

Robotic Devices

Monitoring

Anchor Filtering

10

Desiderata - Geometric Planning• Anchors at the symbolic level need to be evaluated

at a finer level of granularity

• Predicates referring to the 3D world

• Actions that affect 3D world

• Geometric Planning involves

• Maintaining a 3D world state

• Standard 3D motion planning algorithms

Deliberation

Symbolic Planning/Execution

Geometric Planning/Execution

Action Perception

Robotic Devices

Monitoring

Anchor Filtering

11

Desiderata - Monitoring

• Continuous monitoring of acting and sensing required for:

• Critical processes may require realtime reactions — e.g. collision avoidance

• High-level declarative actions — e.g. moving to location

Deliberation

Symbolic Planning/Execution

Geometric Planning/Execution

Action Perception

Robotic Devices

Monitoring

Anchor Filtering

12

Desiderata - Action/Perception to Devices• Action and Perception processing

e.g. ROS services

• Raw sensor data processing

• Complex actuator actions

• Mixed sensor/actuator processes (SLAM)

• Robotic Devices

• Translation to specific device implementation

Deliberation

Symbolic Planning/Execution

Geometric Planning/Execution

Action Perception

Robotic Devices

Monitoring

Anchor Filtering

13

An Instantiation of our Architecture

Instantiation in AgentSpeak(L)• AgentSpeak(L)

• Operationalizes the deliberation and symbolic planning layers

• Many implementations of its semantics, with proven properties

• Key construct: evaluable/geometric predicates

• Main link between Symbolic and Geometric Layers (conceptually filtering)

• Not linked directly to belief base, but a call to external procedure

• Call is mediated by a number of functions in filtering

15

Filtering Layer for AgentSpeak

• Mapping of ground geometric predicates to goal poses — user defined

• Intermediary function — mediates calls to geometric planner

• Intermediary function is called from AgentSpeak preconditions

map : C ⇥ Ps ⇥O1 ⇥ . . .⇥On ! 2C

int : Ps ⇥O1 ⇥ . . .⇥On ! {true, false}10 Name of First Author and Name of Second Author

act : int(ps,o1, . . . ,on) ← body

16

Symbolic)Planning)

Geom

etric)Planning)

Ac3on) Percep3on)

Anchor)Filtering)

10 Name of First Author and Name of Second Author

act : int(ps,o1, . . . ,on) ← body

Contribution Title 9

11. Calfee, R. C., & Valencia, R. R. (1991). APA guide to preparing manuscripts for journalpublication.Washington, DC: American Psychological Association.

12. Dod, J. (1999). Effective substances. In: The dictionary of substances and their effects. RoyalSociety of Chemistry. Available via DIALOG.http://www.rsc.org/dose/Effective substances. Cited 15 Jan 1999.

13. Harris, M., Karper, E., Stacks, G., Hoffman, D., DeNiro, R., Cruz, P., et al. (2001). Writinglabs and the Hollywood connection. J FilmWriting, 44(3), 213–245.

14. O’Neil, J. M., & Egan, J. (1992). Men’s and women’s gender role journeys: Metaphor forhealing, transition, and transformation. In B. R. Wainrig (Ed.), Gender issues across the lifecycle (pp. 107–123). New York: Springer.

15. Kreger, M., Brindis, C.D., Manuel, D.M., Sassoubre, L. (2007). Lessons learned in systemschange initiatives: benchmarks and indicators. American Journal of Community Psychology,doi: 10.1007/s10464-007-9108-14.

16. Alber John, Daniel C. O’Connell, and Sabine Kowal. 2002. Personal perspective in TV inter-views. Pragmatics 12:257–271

17. Cameron, Deborah. 1997. Theoretical debates in feminist linguistics: Questions of sex andgender. In Gender and discourse, ed. Ruth Wodak, 99–119. London: Sage Publications.

18. Cameron, Deborah. 1985. Feminism and linguistic theory. New York: St. Martin’s Press.19. Dod, Jake. 1999. Effective substances. In: The dictionary of substances and their effects.

Royal Society of Chemistry. Available via DIALOG.http://www.rsc.org/dose/title of subordinate document. Cited 15 Jan 1999

20. Suleiman, Camelia, Daniel C. OConnell, and Sabine Kowal. 2002. ‘If you and I, if we, in thislater day, lose that sacred fire...’: Perspective in political interviews. Journal of Psycholin-guistic Research. doi: 10.1023/A:1015592129296.

21. Brown B, Aaron M (2001) The politics of nature. In: Smith J (ed) The rise of modern ge-nomics, 3rd edn. Wiley, New York

22. Dod J (1999) Effective Substances. In: The dictionary of substances and their effects. RoyalSociety of Chemistry. Available via DIALOG.http://www.rsc.org/dose/title of subordinate document. Cited 15 Jan 1999

23. Slifka MK, Whitton JL (2000) Clinical implications of dysregulated cytokine production. JMol Med, doi: 10.1007/s001090000086

24. Smith J, Jones M Jr, Houghton L et al (1999) Future of health insurance. N Engl J Med965:325–329

25. South J, Blass B (2001) The future of modern genomics. Blackwell, London

find valid trajectory from cinit ∈C to any cgoal ∈map(cinit , ps,o1, . . . ,on)

Filtering Layer for AgentSpeak

17

Connecting with Motion Planning• Geometric predicates encapsulated in AgentSpeak plan-rules

• Each predicate gets assigned a unique achievement goal

• Achievement goal handled via success and failure plan-rules

• Plan-bodies have atomic actions calling intermediary function, where action-bodies:

• Execute trajectory found via intermediary function (if any)

• Add resulting facts, or facts explaining why there’s no trajectory18

Connecting with Motion PlanningSymbolic)Planning/Execu3on)

Geometric)Planning/Execu3on)

Ac3on) Percep3on)

Summary Information for Reasoning about Hierarchical Plans

Paper 1339

AbstractHierarchically structured agent plans are impor-tant for efficient planning and acting, and theyalso serve (among other things) to produce “richer”classical plans, composed not just of a sequenceof primitive actions, but also “abstract” ones repre-senting the supplied hierarchies. A crucial step forthis and other approaches is deriving preconditionand effect “summaries” from a given plan hierar-chy. This paper provides mechanisms to do this formore pragmatic and conventional hierarchies thanin the past. To this end, we formally define the no-tion of a precondition and an effect for a hierarchi-cal plan; we present data structures and algorithmsfor automatically deriving this information; and weanalyse the properties of the presented algorithms.We conclude the paper by detailing how our algo-rithms may be used together with a classical plan-ner in order to obtain abstract plans.

Introduction

!ep(v⃗)

ORfailure rule

body1true

actPassp(v⃗)int(p, v⃗)

body⊤; post⊤

body2true

actFailp(v⃗)¬int(p, v⃗)

body⊥; post⊥

EVENT

PLAN-RULE

ACTION

Hierarchically structured agent plans are appealing for ef-ficient planning and acting because they embody an expert’sdomain control knowledge, which can in practice greatlyspeed up the reasoning process. Two popular approachesthat are based on such representations are HTN (Hierar-chical Task Network) [Erol et al., 1994] planning systemsand BDI (Belief-Desire-Intention) [Rao and Georgeff, 1995]agent systems. While HTN planners “look ahead” over a sup-plied collection of hierarchical plans to determine whether atask has a viable decomposition, BDI agents interleave thisprocess with acting in the real world, thereby trading offsolution quality for faster responsiveness to environmentalchanges. Despite these differences, however, HTN and BDIsystems are closely related in both syntax and semantics,

making it possible to translate between the two representa-tions [Sardina et al., 2006].One novel application of such hierarchies has been to pro-

duce “richer” classical plans composed not just of sequencesof primitive actions, but also “abstract” ones representing thesupplied hierarchies [de Silva et al., 2009]. Abstract plans areparticularly appealing in the context of BDI and HTN systemsbecause they respect and re-use the domain control knowl-edge inherent in such systems. Moreover, abstract plans areflexible and robust: if a refinement of one of its abstract ac-tions into a primitive step happens to fail, or it cannot be ap-plied, another option may be tried to achieve the step.This paper provides mechanisms for automatically deriv-

ing abstract actions and plans from the information in asupplied plan hierarchy. Our algorithms for doing this arebased on those of [Clement et al., 2007], which calculateoffline the precondition-summaries and effect-summaries ofHTN-like hierarchical structures that define the agents in amulti-agent system, and then use these summaries at runtimeto coordinate the agents. Related to [Clement et al., 2007]are the summary algorithms of [Thangarajah et al., 2003a;2003b]. A noteworthy difference in the latter work is that“definite-effect” summaries of an entity such as a plan orgoal are any effects that will (definitely) be brought about atany intermediate stage during the execution of the entity. Incontrast, definite-effect summaries in our work and in that ofClement et al. are only those effects that will (definitely) holdat the end of the entity’s execution. A nuance worth mention-ing between our work and that of Clement et al. is that inour work the precondition of an entity is a standard classicalprecondition (with disjunction), and in their work it is (es-sentially) two sets of literals: the ones that must hold at thestart of any successful execution of the entity, and the onesthat must hold at the start of at least one such execution. Themost important difference between the two mentioned worksand ours, however, is that their work is based on propositionallogic, and ours on first-order logic.In [Fritz et al., 2008; Baier et al., 2007] the authors present

algorithms for using domain control knowledge inherent inConGolog/Golog programs as heuristics in classical plan-ning. To this end, they modify planning operators in orderto restrict the applicability of their preconditions, and addextra “bookkeeping” operators to guide the search towarddesired actions in accordance with the control knowledge.

Anchor)Filtering)

19

Computing Symbolic Facts• Action-body obtains domain dependent + independent facts

• Some are computed w.r.t. current pose: e.g. inside(rob1,room1)

• New objects—e.g. cup3—can be discovered and linked to facts

• Domain independent facts describe non-existence of trajectory

• not-reachable(cup1,arm1)— e.g. pick(cup1,arm1) was impossible

• obstructsSome(cup3,cup1,arm1) and obstructsAll(...)

20

Related Work• Dornhege et al. [2009] — ”Semantic-attachments” and ”Effect applicators”

• Kaelbling et al. [2011,2012] — interleaving planning and execution

• Karlsson et al. [2012], Lagriffoul et al. [2012] and de Silva et al. [2013] — combined symbolic geometric backtracking

• Srivastava et al. [2014] — validating classical plans via geometric trajectories

• Erdem et al. [2011] and Plaku and Hager, [2010] — symbolic planner guides the motion planner toward a collision-free trajectory

• Ingrand and Ghallab [2014] — part of the inspiration for this architecture

21

Conclusion and Future Work• Contribution:

• Summarised functionalities present in existing agent systems and robotic systems

• Organised them in a tiered architecture

• Instantiation based on the AgentSpeak(L) language

• Future work: formalise the integration of motion planning in AgentSpeak(L) evaluate an implementation

22

Acknowledgements

• We thank the helpful discussions with

• Amit Kumar Pandey (Aldebaran Robotics, Paris)

• Malik Ghallab (LAAS-CNRS)

• Alexandre Amory (PUCRS)

23

Questions?