meld ldp iros07 talk3

50 %
50 %
Information about meld ldp iros07 talk3
Education

Published on January 7, 2008

Author: Javier

Source: authorstream.com

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

Add a comment

Related presentations

Related pages

Meld: A Declarative Approach to Programming Ensembles

This paper presents Meld, a programming language for modular robots, i.e., for independently executing robots where inter-robot communication is limited to ...
Read more

Meld: A Declarative Approach to Programming Ensembles

This paper presents Meld, ... , year = {2007}, month = {October}, keywords = {Programming Models, Planning, LDP, Meld ... {ashley-rollman-iros07 ...
Read more

Meld: A declarative approach to programming ensembles (PDF ...

Official Full-Text Publication: Meld: A declarative approach to programming ensembles on ResearchGate, the professional network for scientists.
Read more

Distributed Intelligent MEMS: Progresses and Perspectives ...

Official Full-Text Publication: Distributed Intelligent MEMS: Progresses and Perspectives on ResearchGate, the professional network for scientists.
Read more