Masashi Aono

The Boolean satisfiability problem (SAT) is an NP-complete combinatorial optimization problem, where fast SAT solvers are useful for various smart society applications. Since these edge-oriented applications require time-critical control, a high speed SAT solver on FPGA is a promising approach. Here the authors propose a novel FPGA implementation of a bio-inspired stochastic local search algorithm called ‘AmoebaSAT’ on a Zynq board. Previous studies on FPGA-AmoebaSATs tackled relatively smaller-sized 3-SAT instances with a few hundred variables and found the solutions in several milli seconds. These implementations, however, adopted an instance-specific approach, which requires synthesis of FPGA configuration every time when the targeted instance is altered. In this paper, a slimmed version of AmoebaSAT named ‘AmoebaSATslim,’ which omits the most resource-consuming part of interactions among variables, is proposed. The FPGA-AmoebaSATslim enables to tackle significantly larger-sized 3-SAT instances, accepting 30,000 variables with 130, 800 clauses. It achieves up to approximately 24 times faster execution speed than the software-AmoebaSATslim implemented on a CPU of the x86 server.

Domain-specific computing architectures are expected to enable the development of new technologies after the saturation of the performance growth concerning conventional general-purpose computers. One such approach is to develop a combinatorial optimization machine (COM), which enables searching for an approximately optimal solution across a vast number of candidates more rapidly than conventional computers. To achieve the rapidity and optimality of the search, a COM exploits physical processes in specific hardware, exhibiting parallelism and stochasticity. This paper summarizes a unique biologically inspired approach to perform combinatorial optimization, which we have been investigated for over a decade. We first performed a series of biological experiments to evaluate the problem-solving ability of a single-celled amoeba that changes its shape into an optimal one by maximizing its body area for foraging and by minimizing the risk of being exposed to aversive light stimuli. Mathematically modeling the shape-changing dynamics of the amoeba, we formulated two algorithms for solving the traveling salesman problem (TSP) and Boolean satisfiability problem (SAT), named “AmoebaTSP” and “AmoebaSAT,” respectively. AmoebaTSP and AmoebaSAT were implemented using analog and/or digital electronic circuits, to maximize their rapid search performance, by exploiting the parallel and stochastic nature of the circuits. We demonstrated that these COMs, called “electronic amoebae” are advantageous in diverse applications, as they can easily handle arbitrary problem instances of TSP and SAT without any costly preprocessing for problem mapping and their dynamics stabilize only at legal solutions that satisfy all given constraints. As electronic amoebae can be composed of conventional complementary metal-oxide semiconductor devices, they are highly scalable, energy-efficient, and suitable for both cloud- and edge computing applications.

AmbSAT (or AmoebaSAT) is a biologically-inspired stochastic local search (SLS) solver to explore solutions to the Boolean satisfiability problem (SAT). AmbSAT updates multiple variables in parallel at every iteration step, and thus AmbSAT can find solutions with a fewer number of iteration steps than some other conventional SLS solvers for a specific set of SAT instances. However, the parallelism of AmbSAT is not compatible with general-purpose microprocessors in that many clock cycles are required to execute each iteration; thus, AmbSAT requires special hardware that can exploit the parallelism of AmbSAT to quickly find solutions. In this paper, we propose a circuit model (hardware-friendly algorithm) that explores solutions to SAT in a similar way to AmbSAT, which we call circuit-level AmbSAT (CLAmbSAT). We conducted numerical simulation to evaluate the search performance of CL-AmbSAT for a set of randomly generated SAT instances that was designed to estimate the scalability of our approach. Simulation results showed that CLAmbSAT finds solutions with a fewer iteration number than a powerful SLS solver, ProbSAT, and outperforms even AmbSAT. Since CL-AmbSAT uses simple combinational logic to update variables, CL-AmbSAT can be easily implemented in various hardware.

Choosing a better move correctly and quickly is a fundamental skill of living organisms that corresponds to solving a computationally demanding problem. A unicellular plasmodium ofPhysarum polycephalumsearches for a solution to the travelling salesman problem (TSP) by changing its shape to minimize the risk of being exposed to aversive light stimuli. In our previous studies, we reported the results on the eight-city TSP solution. In this study, we show that the time taken by plasmodium to find a reasonably high-quality TSP solution grows linearly as the problem size increases from four to eight. Interestingly, the quality of the solution does not degrade despite the explosive expansion of the search space. Formulating a computational model, we show that the linear-time solution can be achieved if the intrinsic dynamics could allocate intracellular resources to grow the plasmodium terminals with a constant rate, even while responding to the stimuli. These results may lead to the development of novel analogue computers enabling approximate solutions of complex optimization problems in linear time.

Decision making is a vital function in the age of machine learning and artificial intelligence; however, its physical realization and theoretical fundamentals are not yet well understood. In our former study, we demonstrated that single photons can be used to make decisions in uncertain, dynamically changing environments. The two-armed bandit problem was successfully solved using the dual probabilistic and particle attributes of single photons. In this study, we present a category theoretic modeling and analysis of single-photon-based decision making, including a quantitative analysis that agrees well with the experimental results. The category theoretic model unveils complex interdependencies of the entities of the subject matter in the most simplified manner, including a dynamically changing environment. In particular, the octahedral structure and the braid structure in triangulated categories provide better understandings and quantitative metrics of the underlying mechanisms for the single-photon decision maker. This study provides insight and a foundation for analyzing more complex and uncertain problems for machine learning and artificial intelligence.

Decision making is a vital function in this age of machine learning and artificial intelligence, yet its physical realization and theoretical fundamentals are still not completely understood. In our former study, we demonstrated that single-photons can be used to make decisions in uncertain, dynamically changing environments. The two-armed bandit problem was successfully solved using the dual probabilistic and particle attributes of single photons. In this study, we present a category theoretic modeling and analysis of single-photon-based decision making, including a quantitative analysis that is in agreement with the experimental results. A category theoretic model reveals the complex interdependencies of subject matter entities in a simplified manner, even in dynamically changing environments. In particular, the octahedral and braid structures in triangulated categories provide a better understanding and quantitative metrics of the underlying mechanisms of a single-photon decision maker. This study provides both insight and a foundation for analyzing more complex and uncertain problems, to further machine learning and artificial intelligence.

We have developed a bio-inspired electronic computing system, the "electronic amoeba". This system was designed to search for a solution to a combinational optimization problem, as inspired by foraging behavior of a single-celled amoeboid organism that is trying to maximize its food intake while satisfying given constraints. We electronically implement the system and demonstrate its solution search capability for solving the Boolean satisfiability problem, SAT. We apply the electronic amoeba to autonomous walking control of a multi-legged robot. Each leg joint has three-valued state and the electronic amoeba successively searches for a combination of the leg joint states to satisfy the objective of moving straight depending on the state of the robot.

The interaction strength of progressively longer oligomers of glycine, (Gly), di-Gly, tri-Gly, and penta-Gly, with a natural pyrite surface was directly measured using the force mode of an atomic force microscope (AFM). In recent years, selective activation of abiotically formed amino acids on mineral surfaces, especially that of pyrite, has been proposed as an important step in many origins of life scenarios. To investigate such notions, we used AFM-based force measurements to probe possible non-covalent interactions between pyrite and amino acids, starting from the simplest amino acid, Gly. Although Gly itself interacted with the pyrite surface only weakly, progressively larger unbinding forces and binding frequencies were obtained using oligomers from di-Gly to penta-Gly. In addition to an expected increase of the configurational entropy and size-dependent van der Waals force, the increasing number of polar peptide bonds, among others, may be responsible for this observation. The effect of chain length was also investigated by performing similar experiments using l-lysine vs. poly-l-lysine (PLL), and l-glutamic acid vs. poly-l-glutamic acid. The results suggest that longer oligomers/polymers of amino acids can be preferentially adsorbed on pyrite surfaces.

Water creates special problems for prebiotic chemistry, as it is thermodynamically favorable for amide and phosphodiester bonds to hydrolyze. The availability of alternative solvents with more favorable properties for the formation of prebiotic molecules on the early Earth may have helped bypass this so-called “water paradox”. Formamide (FA) is one such solvent, and can serve as a nucleobase precursor, but it is difficult to envision how FA could have been generated in large quantities or accumulated in terrestrial surface environments. We report here the conversion of aqueous acetonitrile (ACN) via hydrogen cyanide (HCN) as an intermediate into FA by γ-irradiation under conditions mimicking exposure to radioactive minerals. We estimate that a radioactive placer deposit could produce 0.1‒0.8 mol FA km⁻² year⁻¹. A uraninite fission zone comparable to the Oklo reactors in Gabon can produce 0.1‒1 mol m⁻² year⁻¹, orders of magnitude greater than other scenarios of FA production or delivery for which reaching sizeable concentrations of FA are problematic. Radioactive mineral deposits may be favorable settings for prebiotic compound formation through emergent geologic processes and FA-mediated organic chemistry.

The tractable history of life records a successive emergence of organisms composed of hierarchically organized cells and greater degrees of individuation. The lowermost object level of this hierarchy is the cell, but it is unclear whether the organizational attributes of living systems extended backward through prebiotic stages of chemical evolution. If the systems biology attributes of the cell were indeed templated upon prebiotic synthetic relationships between subcellular objects, it is not obvious how to categorize object levels below the cell in ways that capture any hierarchies which may have preceded living systems. In this paper, we map out stratified relationships between physical components that drive the production of key prebiotic molecules starting from radiolysis of a small number of abundant molecular species. Connectivity across multiple levels imparts the potential to create and maintain far‐from‐equilibrium chemical conditions and to manifest nonlinear system behaviors best approximated using automata formalisms. The architectural attribute of “information hiding” of energy exchange processes at each object level is shared with stable, multitiered automata such as digital computers. These attributes may indicate a profound connection between the system complexity afforded by energy dissipation by subatomic level objects and the emergence of complex automata that could have preceded biological systems.