The Experts below are selected from a list of 199491 Experts worldwide ranked by ideXlab platform
Sébastien Tixeuil - One of the best experts on this subject based on the ideXlab platform.
-
Arbitrary Pattern Formation with Four Robots
2018Co-Authors: Quentin Bramas, Sébastien TixeuilAbstract:The Pattern Formation problem by autonomous mobile robots has been extensively studied and is at the core of oblivious mobile robots literature. However remaining cases involving few robots are still open. In this paper we propose a new geometric invariant that exists in any configuration with four robots. We then use this invariant to solve the Pattern Formation problem with four robots, with or without the common chirality assumption.
-
SSS - Arbitrary Pattern Formation with Four Robots
Lecture Notes in Computer Science, 2018Co-Authors: Quentin Bramas, Sébastien TixeuilAbstract:The Pattern Formation problem by autonomous mobile robots has been extensively studied and is at the core of oblivious mobile robots literature. However remaining cases involving few robots are still open. In this paper we propose a new geometric invariant that exists in any configuration with four robots. We then use this invariant to solve the Pattern Formation problem with four robots, with or without the common chirality assumption.
-
Probabilistic Asynchronous Arbitrary Pattern Formation (Short Paper)
2016Co-Authors: Quentin Bramas, Sébastien TixeuilAbstract:We propose a new probabilistic Pattern Formation algorithm for oblivious mobile robots that operates in the ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinate systems of robots (the robots do not share a common “North” nor a common “Right”), yet it preserves the ability from any initial configuration that contains at least 5 robots to form any general Pattern (and not just Patterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in the same model) that robots do not pause while moving (so, our robots really are fully asynchronous), and the amount of randomness is kept low – a single random bit per robot per Look-Compute-Move cycle is used. Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministic Pattern Formation one. As the deterministic phase does not use chirality, it may be of independent interest in the deterministic context. A noteworthy feature of our algorithm is the ability to form Patterns with multiplicity points (except the gathering case due to impossibility results), a new feature in the context of Pattern Formation that we believe is an important asset of our approach.
-
Brief announcement: Probabilistic Asynchronous Arbitrary Pattern Formation
2016Co-Authors: Quentin Bramas, Sébastien TixeuilAbstract:We propose a new probabilistic Pattern Formation algorithm for oblivious mobile robots that operates in the ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinate systems of robots (the robots do not share a common ``North'' nor a common ``Right''), yet it preserves the ability from any initial configuration that contains at least 5 robots to form any general Pattern (and not just Patterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in the same model) that robots do not pause while moving (so, our robots really are fully asynchronous), and the amount of randomness is kept low -- a single random bit per robot per Look-Compute-Move cycle is used. Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministic Pattern Formation one. As the deterministic phase does not use chirality, it may be of independent interest in the deterministic context. A noteworthy feature of our algorithm is the ability to form Patterns with multiplicity points, a new feature in the context of Pattern Formation that we believe is an important asset of our approach.
-
Probabilistic Asynchronous Arbitrary Pattern Formation
2015Co-Authors: Quentin Bramas, Sébastien TixeuilAbstract:We propose a new probabilistic Pattern Formation algorithm for oblivious mobile robots that operates in the ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinate systems of robots (the robots do not share a common “North” nor a common “Right”), yet it preserves the ability from any initial configuration that contains at least 5 robots to form any general Pattern (and not just Patterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in the same model) that robots do not pause while moving (so, our robots really are fully asynchronous), and the amount of randomness is kept low – a single random bit per robot per Look-Compute-Move cycle is used. Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministic Pattern Formation one. As the deterministic phase does not use chirality, it may be of independent interest in the deterministic context. A noteworthy feature of our algorithm is the ability to form Patterns with multiplicity points (except the gathering case due to impossibility results), a new feature in the context of Pattern Formation that we believe is an important asset of our approach.
Quentin Bramas - One of the best experts on this subject based on the ideXlab platform.
-
Arbitrary Pattern Formation with Four Robots
2018Co-Authors: Quentin Bramas, Sébastien TixeuilAbstract:The Pattern Formation problem by autonomous mobile robots has been extensively studied and is at the core of oblivious mobile robots literature. However remaining cases involving few robots are still open. In this paper we propose a new geometric invariant that exists in any configuration with four robots. We then use this invariant to solve the Pattern Formation problem with four robots, with or without the common chirality assumption.
-
SSS - Arbitrary Pattern Formation with Four Robots
Lecture Notes in Computer Science, 2018Co-Authors: Quentin Bramas, Sébastien TixeuilAbstract:The Pattern Formation problem by autonomous mobile robots has been extensively studied and is at the core of oblivious mobile robots literature. However remaining cases involving few robots are still open. In this paper we propose a new geometric invariant that exists in any configuration with four robots. We then use this invariant to solve the Pattern Formation problem with four robots, with or without the common chirality assumption.
-
Probabilistic Asynchronous Arbitrary Pattern Formation (Short Paper)
2016Co-Authors: Quentin Bramas, Sébastien TixeuilAbstract:We propose a new probabilistic Pattern Formation algorithm for oblivious mobile robots that operates in the ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinate systems of robots (the robots do not share a common “North” nor a common “Right”), yet it preserves the ability from any initial configuration that contains at least 5 robots to form any general Pattern (and not just Patterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in the same model) that robots do not pause while moving (so, our robots really are fully asynchronous), and the amount of randomness is kept low – a single random bit per robot per Look-Compute-Move cycle is used. Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministic Pattern Formation one. As the deterministic phase does not use chirality, it may be of independent interest in the deterministic context. A noteworthy feature of our algorithm is the ability to form Patterns with multiplicity points (except the gathering case due to impossibility results), a new feature in the context of Pattern Formation that we believe is an important asset of our approach.
-
Brief announcement: Probabilistic Asynchronous Arbitrary Pattern Formation
2016Co-Authors: Quentin Bramas, Sébastien TixeuilAbstract:We propose a new probabilistic Pattern Formation algorithm for oblivious mobile robots that operates in the ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinate systems of robots (the robots do not share a common ``North'' nor a common ``Right''), yet it preserves the ability from any initial configuration that contains at least 5 robots to form any general Pattern (and not just Patterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in the same model) that robots do not pause while moving (so, our robots really are fully asynchronous), and the amount of randomness is kept low -- a single random bit per robot per Look-Compute-Move cycle is used. Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministic Pattern Formation one. As the deterministic phase does not use chirality, it may be of independent interest in the deterministic context. A noteworthy feature of our algorithm is the ability to form Patterns with multiplicity points, a new feature in the context of Pattern Formation that we believe is an important asset of our approach.
-
Probabilistic Asynchronous Arbitrary Pattern Formation
2015Co-Authors: Quentin Bramas, Sébastien TixeuilAbstract:We propose a new probabilistic Pattern Formation algorithm for oblivious mobile robots that operates in the ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinate systems of robots (the robots do not share a common “North” nor a common “Right”), yet it preserves the ability from any initial configuration that contains at least 5 robots to form any general Pattern (and not just Patterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in the same model) that robots do not pause while moving (so, our robots really are fully asynchronous), and the amount of randomness is kept low – a single random bit per robot per Look-Compute-Move cycle is used. Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministic Pattern Formation one. As the deterministic phase does not use chirality, it may be of independent interest in the deterministic context. A noteworthy feature of our algorithm is the ability to form Patterns with multiplicity points (except the gathering case due to impossibility results), a new feature in the context of Pattern Formation that we believe is an important asset of our approach.
James D. Murray - One of the best experts on this subject based on the ideXlab platform.
-
An Envelope Method for Analyzing Sequential Pattern Formation
SIAM Journal on Applied Mathematics, 2000Co-Authors: Gerhard C. Cruywagen, Philip K. Maini, James D. MurrayAbstract:We examine sequential spatial Pattern Formation in a tissue interaction model for skin organ morphogenesis. Pattern Formation occurs as a front sweeps across the domain leaving in its wake a steady state spatial Pattern. Extensive numerical simulations show that these fronts travel with constant wave speed. By considering the envelope of the solution profile we present a novel method of calculating its wave speed.
-
Sequential Pattern Formation in a model for skin morphogenesis.
Mathematical Medicine and Biology, 1992Co-Authors: Gerhard C. Cruywagen, Philip K. Maini, James D. MurrayAbstract:During morphogenesis regular Patterns often develop behind a frontier of Pattern Formation which travels across the prospective tissue. Here the authors consider the propagating Patterns exhibited in a two-dimensional domain by a tissue interaction mechanochemical model for skin Pattern Formation. It is shown that the model can exhibit travelling waves of complex spatial Pattern Formation. Two alternative mechanisms that can produce such sequential Patterning are presented. In particular, it is demonstrated that the specification of a simple quasi-one-dimensional Pattern is all that is required to determine a complex two-dimensional Pattern. Finally, the model solutions are related to actual Pattern propagation during chick feather primordia initiation.
-
Pattern selection in biological Pattern Formation mechanisms
Applied Mathematics Letters, 1991Co-Authors: D. E. Bentil, James D. MurrayAbstract:Abstract Realistic Pattern Formation models in biology usually have several parameters. The determination of sets of parameter values which generate specific Patterns is not an easy problem. We describe a simple, systematic method for choosing such parameter values and, by way of example, apply it to one of the new mechanochemical models for biological Pattern Formation which has nine parameters.
Gerhard C. Cruywagen - One of the best experts on this subject based on the ideXlab platform.
-
An Envelope Method for Analyzing Sequential Pattern Formation
SIAM Journal on Applied Mathematics, 2000Co-Authors: Gerhard C. Cruywagen, Philip K. Maini, James D. MurrayAbstract:We examine sequential spatial Pattern Formation in a tissue interaction model for skin organ morphogenesis. Pattern Formation occurs as a front sweeps across the domain leaving in its wake a steady state spatial Pattern. Extensive numerical simulations show that these fronts travel with constant wave speed. By considering the envelope of the solution profile we present a novel method of calculating its wave speed.
-
Tissue interaction and spatial Pattern Formation
1992Co-Authors: Gerhard C. CruywagenAbstract: The development of spatial structure and form on vertebrate skin is a complex and poorly understood phenomenon. We consider here a new mechanochemical tissue interaction model for generating vertebrate skin Patterns. Tissue interaction, which plays a crucial role in vertebrate skin morphogenesis, is modelled by reacting and diffusing signal morphogens. The model consists of seven coupled partial differential equations, one each for dermal and epidermal cell densities, four for the signal morphogen concentrations and one for describing epithelial mechanics. Because of its complexity, we reduce the full model to a small strain quasi-steady-state model, by making several simplifying assumptions. A steady state analysis demonstrates that our reduced system possesses stable time-independent steady state solutions on one-dimensional spatial domains. A linear analysis combined with a multiple time-scale perturbation procedure and numerical simulations are used to examine the range of Patterns that the model can exhibit on both one- and two-dimensions domains. Spatial Patterns, such as rolls, squares, rhombi and hexagons, which are remarkably similar to those observed on vertebrate skin, are obtained. Although much of the work on Pattern Formation is concerned with synchronous spatial Patterning, many structures on vertebrate skin are laid down in a sequential fashion. Our tissue interaction model can account for such sequential Pattern Formation. A linear analysis and a regular perturbation analysis is used to examine propagating epithelial contraction waves coupled to dermal cell invasion waves. The results compare favourably with those obtained from numerical simulations of the model. Furthermore, sequential Pattern Formation on one-dimensional domains is analysed; first by an asymptotic technique, and then by a new method involving the envelopes of the spatio-temporal propagating solutions. Both methods provide analytical estimates for the speeds of the wave of propagating Pattern which are in close agreement with those obtained numerically. Finally, by numerical simulations, we show that our tissue interaction model can account for two-dimensional sequential Pattern Formation. In particular, we show that complex two-dimensional Patterns can be determined by simple quasi-one-dimensional Patterns.
-
Sequential Pattern Formation in a model for skin morphogenesis.
Mathematical Medicine and Biology, 1992Co-Authors: Gerhard C. Cruywagen, Philip K. Maini, James D. MurrayAbstract:During morphogenesis regular Patterns often develop behind a frontier of Pattern Formation which travels across the prospective tissue. Here the authors consider the propagating Patterns exhibited in a two-dimensional domain by a tissue interaction mechanochemical model for skin Pattern Formation. It is shown that the model can exhibit travelling waves of complex spatial Pattern Formation. Two alternative mechanisms that can produce such sequential Patterning are presented. In particular, it is demonstrated that the specification of a simple quasi-one-dimensional Pattern is all that is required to determine a complex two-dimensional Pattern. Finally, the model solutions are related to actual Pattern propagation during chick feather primordia initiation.
Stefano Longhi - One of the best experts on this subject based on the ideXlab platform.
-
Nonadiabatic effects in optical Pattern Formation
Physical Review A, 2001Co-Authors: Stefano LonghiAbstract:Pattern Formation in cavity nonlinear optical systems subjected to a periodic modulation of frequency detuning is studied analytically and numerically with particular reference to the models of optical parametric oscillator and two-level laser. Owing to the nonautonomous dynamics, a new mechanism for Pattern Formation as a result of a primary instability, rather distinct from the most common tilted-wave mechanism found in autonomous systems, is predicted and explained in detail by means of a phase integral (WKB) analysis of the underlying field equations. This mechanism for Pattern Formation can be traced back to the existence of coherent field oscillations in the two-field dynamics and associated to the existence of turning points in the WKB expansion, which break the adiabatic following. In particular, it is shown that nonadiabatic effects are likely when the decay rates of interacting fields are equal, corresponding to the existence of real turning points. For different relaxation rates of interacting fields, the turning points are complex and nonadiabatic effects vanish at low modulation frequencies. Above threshold, weakly nonlinear analysis and numerical simulations indicate that traveling waves are selected by the nonlinearity.
-
Nonadiabatic effects in optical Pattern Formation
Conference Digest. 2000 International Quantum Electronics Conference (Cat. No.00TH8504), 1Co-Authors: Stefano LonghiAbstract:Summary form only given. Tuning instability leading to Pattern Formation in cavity nonlinear optics is generally described in terms of a tilted-wave mechanism that provides a simple geometric and linear picture of the fact that diffractive off-axis waves can fit the cavity resonance allowing maximum energy extraction from the medium. In mean-field models the tilted wave mechanism is effective solely when the resonated field is blue-shifted from the nearby cavity resonance. And off-axis waves are generally prevented on the other side of cavity resonance. A rather novel mechanism for Pattern Formation, that permits off-axis emission also on the red side of cavity resonance, is proposed and studied. This mechanism for off-axis wave emission occurs in presence of a time-varying periodic detuning; since this mechanism becomes ineffective when the modulation frequency of detuning is either fast or slow as compared to the typical relaxational dynamics of the system, it is referred as nonadiabatic. A detailed analysis of nonadiabatic effects on Pattern Formation are presented for the of a doubly-resonant degenerate optical parametric oscillator (DOPO).
