We consider the following class of polygon-constrained motion planning problems: Given a set ofkcentrally controlled mobile agents (saypebbles) initially sitting on the vertices of ann-vertex simple polygonP, we study how to plan their vertex-to-vertex motion in order to reach with a minimum (eithermaximumortotal) movement (either in terms ofnumber of hopsorEuclidean distance) a final placement enjoying a given requirement. In particular, we focus on final configurations aim-ing at establishing some sort of visual connectivity among the pebbles, which in turn allows for wireless and optical intercommunication. There-fore, after analyzing the notable (and computationally tractable) case of gathering the pebbles at asingle vertex (i.e., the so-calledrendez-vous), we face the problems induced by the requirement that pebbles have eventually to be placed at: (i) a set of vertices that form aconnected subgraph of thevisibility graphinduced by P,sayG(P)(connectivity), and (ii) a set of vertices that form acliqueofG(P)(clique-connectivity). We will show that these two problems are actually hard to approxi-mate, even for the seemingly simpler case in which the hop distance is considered.

Polygon-Constrained Motion Planning Problems

D. Bilò;PROIETTI, GUIDO;
2013

Abstract

We consider the following class of polygon-constrained motion planning problems: Given a set ofkcentrally controlled mobile agents (saypebbles) initially sitting on the vertices of ann-vertex simple polygonP, we study how to plan their vertex-to-vertex motion in order to reach with a minimum (eithermaximumortotal) movement (either in terms ofnumber of hopsorEuclidean distance) a final placement enjoying a given requirement. In particular, we focus on final configurations aim-ing at establishing some sort of visual connectivity among the pebbles, which in turn allows for wireless and optical intercommunication. There-fore, after analyzing the notable (and computationally tractable) case of gathering the pebbles at asingle vertex (i.e., the so-calledrendez-vous), we face the problems induced by the requirement that pebbles have eventually to be placed at: (i) a set of vertices that form aconnected subgraph of thevisibility graphinduced by P,sayG(P)(connectivity), and (ii) a set of vertices that form acliqueofG(P)(clique-connectivity). We will show that these two problems are actually hard to approxi-mate, even for the seemingly simpler case in which the hop distance is considered.
978-3-642-45345-8
File in questo prodotto:
File Dimensione Formato  
c51.pdf

non disponibili

Licenza: Non specificato
Dimensione 539.18 kB
Formato Adobe PDF
539.18 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/42248
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact