Reversibility and Evolution in Automata and Robotics

Reversibility, Evolution, and Power Efficiency in Automata and Robotics

The recent developments in the field of automata theory and robotics have shown a significant shift towards exploring reversibility, evolutionary computation, and power efficiency. Reversibility in automata is being extensively studied, with new variants and hierarchies being proposed to understand their expressive power and computational limits. Notably, the concept of reversible finite automata is being expanded to include multiple initial states and different passes over input strings, revealing complex hierarchies and collapsing properties in certain cases.

Evolutionary computation is also seeing innovative applications, particularly in the design of automata that can evolve over generations. These evolutionary automata offer a dual model to traditional evolutionary algorithms, providing a more formal and precise approach to modeling evolutionary processes. This advancement allows for the direct modeling of the evolution of evolution, hinting at the potential expressiveness and power of natural evolution.

In the realm of robotics, there is a strong focus on developing power-efficient actuators for insect-scale autonomous underwater vehicles (AUVs). Recent breakthroughs have led to the creation of microactuators that operate efficiently both in air and underwater, significantly advancing the feasibility of AUVs at this scale. Additionally, generative design methods using evolutionary algorithms and intrinsic motivation are being employed to create diverse and efficient robot designs, addressing computational costs and premature convergence issues.

Noteworthy Papers:

  • A paper on reversible finite automata establishes a hierarchy by expressive power, highlighting the complexity of different variants.
  • An innovative approach to evolutionary computation models automata that evolve over generations, offering a dual model to traditional evolutionary algorithms.
  • A significant advancement in power-efficient actuators for AUVs paves the way for insect-scale autonomous underwater vehicles.

Sources

A hierarchy of reversible finite automata

Synchronisability in Mailbox Communication

Semantics for Linear-time Temporal Logic with Finite Observations

Expansion Laws for Forward-Reverse, Forward, and Reverse Bisimilarities via Proved Encodings

One Energy Game for the Spectrum between Branching Bisimilarity and Weak Trace Semantics

Evolutionary Automata and Deep Evolutionary Computation

Temporally Non-Uniform Cellular Automata (t-NUCA): Reversibility and Cyclic behavior

Power-Efficient Actuation for Insect-Scale Autonomous Underwater Vehicles

Efficient and Diverse Generative Robot Designs using Evolution and Intrinsic Motivation

A Talent-infused Policy-gradient Approach to Efficient Co-Design of Morphology and Task Allocation Behavior of Multi-Robot Systems

Built with on top of