meld ldp iros07 talk3

Information about meld ldp iros07 talk3

Published on January 7, 2008

Author: Javier

Source: authorstream.com

Content

Declarative Programming for Modular Robots Ashley-Rollman, De Rosa, Srinivasa, Pillai, Goldstein, Campbell:  Declarative Programming for Modular Robots Ashley-Rollman, De Rosa, Srinivasa, Pillai, Goldstein, Campbell November 2, 2007 Locally Distributed Predicates (LDP) & Meld :  Locally Distributed Predicates (LDP) & Meld Two very different approaches to declarative programming for modular robots Meld - logic programming LDP - distributed pattern matching Both achieve higher goals Dramatically shorter code Automatically distributed Automatic messaging LDP Overview:  LDP Overview Originated in Distributed Watchpoint system Needed to describe and detect incorrect distributed state configurations Locally Distributed Predicates Locally Distributed: involving a bounded number of connected modules Predicates: boolean expressions over state, temporal, and topological variables An LDP program consists of a number of predicates, each with one or more attached actions Every predicate/action pair is executed in parallel Meld Overview:  Meld Overview Logic programming language Inspired by P2 [Loo et. al. 2005] Consists of facts and rules for deriving new facts When a fact changes, derived facts are automatically deleted Programs typically consider local neighborhoods Additional support for making non-local neighborhoods LDP and Meld: A Comparison:  LDP and Meld: A Comparison Example: 3D Shape Change Algorithm:  Example: 3D Shape Change Algorithm <20 lines of Meld or LDP Connectivity maintenance guaranteed by algorithm Example 1: Setting Module State:  Example 1: Setting Module State If the module is the seed Set the seed’s state to FINAL For every module inside the target shape If it is next to a module in FINAL state Set the module’s state to FINAL forall (a) where (a.isSeed) do a.state = FINAL; forall (a,b) where (a.state = FINAL) & (b.inside) do b.state = FINAL; type state(module, min int). state(A, FINAL) :- isSeed(A). state(B, FINAL) :- neighbor(A, B), state(A, FINAL), in(B). LDP Meld LDP and Meld: A Comparison:  LDP and Meld: A Comparison Example 2: Evaluation Over all Neighbors:  Example 2: Evaluation Over all Neighbors A module can only be deleted if none of its neighbors are children We first determine which neighbors are not children If there are no children, the module can be deleted type deletable(module). type notChild(module, module). notChild(A, B) :- neighbor(A, B), parent(B, C), A != C. deletable(A) :- forall neighbor(A, B) notChild(A, B). forall(a,b) where (b.parent != a.id) do a.$notChild.add(b.id); forall(a) where size(a.$notChild) = size(a.$neighbors) do a.delete(); LDP Meld LDP and Meld: A Comparison:  LDP and Meld: A Comparison Example 3: Self-deleting Gradients:  Example 3: Self-deleting Gradients Example 3: Self-deleting Gradients:  Example 3: Self-deleting Gradients Meld deletes all dependent facts when the root fact is deleted LDP directly manipulates state variables, so retraction must be manual LDP must specify the maximum number of neighbors forall (a,b) where (a.value > b.value) do a.value = b.value + 1; forall (a,b[0,6]) where count(a.value > b[i].value) = 0 & a.value != 0 do a.value = INF; type gradient (module, min int). gradient(A, N) :- neighbor(A, B), gradient(B, M), N = M + 1. LDP Meld LDP and Meld: A Comparison:  LDP and Meld: A Comparison Example 4: Spanning Tree Creation:  Example 4: Spanning Tree Creation Example 4: Spanning Tree Creation:  Example 4: Spanning Tree Creation Newer versions of Meld use the “first” aggregate to ensure uniqueness This qualifier is not sufficient for more complex situations type parent(module, first module). parent(A, A) :- root(A). parent(B, A) :- neighbor(B, A), parent(A, _). forall (a) where (a.isRoot = 1) do a.parent = a.id; forall (a,b) where (a.parent != -1) & (b.parent = -1) do b.parent = a.id: Example 4b: Spanning Tree Creation:  Example 4b: Spanning Tree Creation Without “first”, Meld must use timestamps to ensure exactly one unique parent LDP uses a single state variable, and thus can never have more than one parent forall (a) where (a.isRoot = 1) do a.parent = a.id; forall (a,b) where (a.parent != -1) & (b.parent = -1) do b.parent = a.id: type possibleParent(module, module, int). type bestParent(module, min int). type parent(module, module). parent(A, A) :- root(A). possibleParent(B, A, T) :- neighbor(A, B), parent(A, _) , T = localTimeStamp(). bestParent(B, T) :- possibleParent(B, _, T). parent(B, A) :- possibleParent(B, A, T), bestParent(B, T). LDP and Meld: A Comparison:  LDP and Meld: A Comparison Future Research:  Future Research • Performance enhancements/optimizations Additional language features Support transactions Applicability to other application domains Explore tradeoffs between automated and manual state control Find a balance that allows programmers to maintain state while gaining some or all of the benefits of automated state Interested in Meld/LDP? Email [mderosa,mpa]@cs.cmu.edu

Related presentations


Other presentations created by Javier

wap
26. 11. 2007
0 views

wap

PairashThajchayapong1
02. 01. 2008
0 views

PairashThajchayapong1

Lecture13 1
09. 10. 2007
0 views

Lecture13 1

Physical Features of Arab World
24. 10. 2007
0 views

Physical Features of Arab World

arbovirus
24. 10. 2007
0 views

arbovirus

Ch14 Lecture
29. 11. 2007
0 views

Ch14 Lecture

going in 13may02
01. 12. 2007
0 views

going in 13may02

cap3
14. 11. 2007
0 views

cap3

enfoques 4 ppt
15. 11. 2007
0 views

enfoques 4 ppt

DeafTalk
16. 11. 2007
0 views

DeafTalk

db2
19. 11. 2007
0 views

db2

REACH Overview
05. 12. 2007
0 views

REACH Overview

Romantic English Literature
14. 12. 2007
0 views

Romantic English Literature

Treaty of Versailles
23. 12. 2007
0 views

Treaty of Versailles

conman15
28. 12. 2007
0 views

conman15

intro CS 1
04. 01. 2008
0 views

intro CS 1

Radiation Concepts
04. 01. 2008
0 views

Radiation Concepts

Kryptologie Folien Web
05. 01. 2008
0 views

Kryptologie Folien Web

bird
29. 10. 2007
0 views

bird

Ideal Year 2006
02. 11. 2007
0 views

Ideal Year 2006

Saggia Ecologia Presentazione
01. 10. 2007
0 views

Saggia Ecologia Presentazione

Royal Europe consumer
30. 10. 2007
0 views

Royal Europe consumer

Undergrat Presentation 2004
24. 10. 2007
0 views

Undergrat Presentation 2004

report pixel2000
01. 11. 2007
0 views

report pixel2000

Johnson 1
06. 11. 2007
0 views

Johnson 1

USA Presentation Rev 4
08. 11. 2007
0 views

USA Presentation Rev 4

Divisenko
20. 11. 2007
0 views

Divisenko

Civil Society Index Project
23. 11. 2007
0 views

Civil Society Index Project

Unit07Log
01. 11. 2007
0 views

Unit07Log

presentaz roma trieste 4
29. 10. 2007
0 views

presentaz roma trieste 4

Montana Meth Presentation
27. 12. 2007
0 views

Montana Meth Presentation

careerbuilder
20. 02. 2008
0 views

careerbuilder

Brussels 11May06
25. 10. 2007
0 views

Brussels 11May06

EDMT14
27. 02. 2008
0 views

EDMT14

pisanelli
30. 10. 2007
0 views

pisanelli

Newch6www
29. 02. 2008
0 views

Newch6www

tunnista kulutustyyppisi
05. 11. 2007
0 views

tunnista kulutustyyppisi

StratTac06 Leggett
05. 03. 2008
0 views

StratTac06 Leggett

Teela powerpoint 6
14. 03. 2008
0 views

Teela powerpoint 6

67436
27. 03. 2008
0 views

67436

dli20071
30. 03. 2008
0 views

dli20071

GEP2007
25. 10. 2007
0 views

GEP2007

hort2 floraldesign
11. 12. 2007
0 views

hort2 floraldesign

Kodal MALTA
04. 10. 2007
0 views

Kodal MALTA

bcs 03 nottingham
26. 11. 2007
0 views

bcs 03 nottingham

17 Sussex
17. 12. 2007
0 views

17 Sussex

asdc ncss for website ihc
06. 11. 2007
0 views

asdc ncss for website ihc

frieman
15. 11. 2007
0 views

frieman

Sem Grd Ontology
19. 11. 2007
0 views

Sem Grd Ontology

Underground1
06. 12. 2007
0 views

Underground1

Avape Port
16. 11. 2007
0 views

Avape Port

ceciliat2
28. 12. 2007
0 views

ceciliat2

diane guatelli
31. 10. 2007
0 views

diane guatelli

cacti
12. 12. 2007
0 views

cacti

Attila Vitai Vodafone
26. 11. 2007
0 views

Attila Vitai Vodafone

kevin dustin
13. 11. 2007
0 views

kevin dustin

02 Italy Gorgucci
31. 10. 2007
0 views

02 Italy Gorgucci

wp4status russia2
26. 10. 2007
0 views

wp4status russia2