BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Giovanni Viglietta

Giovanni Viglietta contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational GeometryMultiagent SystemsRoboticsComputational ComplexityComputer Science and Game TheoryDistributed, Parallel, and Cluster Computing

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2020arXiv

Mobile RAM and Shape Formation by Programmable Particles

We investigate computational issues in the distributed model Amoebots of programmable matter. In this model, the computational entities, called particles, are anonymous finite-state machines that operate and move on an hexagonal tasselation of the plane. In this paper we show how a constant number of such weak particles can simulate a powerful Turing-complete entity that is able to move on the plane while computing. We then show an application of our tool to the classical Shape-Formation problem, providing a new and much more general distributed solution protocol. Indeed, the existing algorithms would allow to form only shapes made of arrangements of segments and triangles. Our algorithm allows the particles to form more abstract and general connected shapes, including circles and spirals, as well as fractal objects of non-integer dimension, such as the Sierpinski triangle or the Koch snowflake. In lieu of the existing limitation on the formability of a shape depending on the symmetry of the initial configuration of the particles, our result provides a complete characterization of the connected shapes that can be formed by an initially simply connected set of particles. Furthermore, in the case of non-connected shapes, we give almost-matching necessary and sufficient conditions for their formability.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Gaming is a hard job, but someone has to do it!

We establish some general schemes relating the computational complexity of a video game to the presence of certain common elements or mechanics, such as destroyable paths, collectible items, doors opened by keys or activated by buttons or pressure plates, etc. Then we apply such "metatheorems" to several video games published between 1980 and 1998, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble~3, and Starcraft. We obtain both new results, and improvements or alternative proofs of previously known results.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Rendezvous of Two Robots with Constant Memory

We study the impact that persistent memory has on the classical rendezvous problem of two mobile computational entities, called robots, in the plane. It is well known that, without additional assumptions, rendezvous is impossible if the entities are oblivious (i.e., have no persistent memory) even if the system is semi-synchronous (SSynch). It has been recently shown that rendezvous is possible even if the system is asynchronous (ASynch) if each robot is endowed with O(1) bits of persistent memory, can transmit O(1) bits in each cycle, and can remember (i.e., can persistently store) the last received transmission. This setting is overly powerful. In this paper we weaken that setting in two different ways: (1) by maintaining the O(1) bits of persistent memory but removing the communication capabilities; and (2) by maintaining the O(1) transmission capability and the ability to remember the last received transmission, but removing the ability of an agent to remember its previous activities. We call the former setting finite-state (FState) and the latter finite-communication (FComm). Note that, even though its use is very different, in both settings, the amount of persistent memory of a robot is constant. We investigate the rendezvous problem in these two weaker settings. We model both settings as a system of robots endowed with visible lights: in FState, a robot can only see its own light, while in FComm a robot can only see the other robot's light. We prove, among other things, that finite-state robots can rendezvous in SSynch, and that finite-communication robots are able to rendezvous even in ASynch. All proofs are constructive: in each setting, we present a protocol that allows the two robots to rendezvous in finite time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Hardness of Mastermind

Mastermind is a popular board game released in 1971, where a codemaker chooses a secret pattern of colored pegs, and a codebreaker has to guess it in several trials. After each attempt, the codebreaker gets a response from the codemaker containing some information on the number of correctly guessed pegs. The search space is thus reduced at each turn, and the game continues until the codebreaker is able to find the correct code, or runs out of trials. In this paper we study several variations of #MSP, the problem of computing the size of the search space resulting from a given (possibly fictitious) sequence of guesses and responses. Our main contribution is a proof of the #P-completeness of #MSP under parsimonious reductions, which settles an open problem posed by Stuckman and Zhang in 2005, concerning the complexity of deciding if the secret code is uniquely determined by the previous guesses and responses. Similarly, #MSP stays #P-complete under Turing reductions even with the promise that the search space has at least k elements, for any constant k. (In a regular game of Mastermind, k=1.) All our hardness results hold even in the most restrictive setting, in which there are only two available peg colors, and also if the codemaker's responses contain less information, for instance like in the so-called single-count (black peg) Mastermind variation.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Rendezvous of two robots with visible bits

We study the rendezvous problem for two robots moving in the plane (or on a line). Robots are autonomous, anonymous, oblivious, and carry colored lights that are visible to both. We consider deterministic distributed algorithms in which robots do not use distance information, but try to reduce (or increase) their distance by a constant factor, depending on their lights' colors. We give a complete characterization of the number of colors that are necessary to solve the rendezvous problem in every possible model, ranging from fully synchronous to semi-synchronous to asynchronous, rigid and non-rigid, with preset or arbitrary initial configuration. In particular, we show that three colors are sufficient in the non-rigid asynchronous model with arbitrary initial configuration. In contrast, two colors are insufficient in the rigid asynchronous model with arbitrary initial configuration and in the non-rigid asynchronous model with preset initial configuration. Additionally, if the robots are able to distinguish between zero and non-zero distances, we show how they can solve rendezvous and detect termination using only three colors, even in the non-rigid asynchronous model with arbitrary initial configuration.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Survey on Open Problems for Mobile Robots

Gathering mobile robots is a widely studied problem in robotic research. This survey first introduces the related work, summarizing models and results. Then, the focus shifts on the open problem of gathering fat robots. In this context, "fat" means that the robot is not represented by a point in a bidimensional space, but it has an extent. Moreover, it can be opaque in the sense that other robots cannot "see through" it. All these issues lead to a redefinition of the original problem and an extension of the CORDA model. For at most 4 robots an algorithm is provided in the literature, but is gathering always possible for n>4 fat robots? Another open problem is considered: Boundary Patrolling by mobile robots. A set of mobile robots with constraints only on speed and visibility is working in a polygonal environment having boundary and possibly obstacles. The robots have to perform a perpetual movement (possibly within the environment) so that the maximum timespan in which a point of the boundary is not being watched by any robot is minimized.

0 citations0 reviewsNo code linkedOpen access