Tozier’s Truchet Tasks

Posted on by
Reply

I’ve spent some time in the last few weeks working on a draft of my long-promised book on “pragmatic” genetic programming. Being a big-P Pragmatist (which is what the title means), I find a big part of the work focuses on useful and/or engaging examples and exercises.

Here’s one I chose to work on in the coming weeks. You might find it of interest.

To be honest, I think the mathematics and computer science needed to address the tasks I’ve set here are not only advanced, but probably a bit unknown. I’ve done a cursory background search, and found (as I suspected) that there’s a lot of useful modeling out there, but scant progress in terms of algorithms.

These are hard problems, in other words. Can you even do them by hand?

Yay for hard problems. If it weren’t for those, life would be so boring.

Items of some interest:

Posted on by

These are my recent Pinboard.in links:

  • Welcome to the Group Pattern Language Project | Group Works

    "This deck of 91 full-colour cards names what skilled facilitators and other participants do to make things work.  The content is more specific than values and less specific than tips and techniques, cutting across existing methodologies with a designer's eye to capture the patterns that repeat.  The deck can be used to plan sesssions, reflect on and debrief them, provide guidance, and share responsibility for making the process go well.  It has the potential to provide a common reference point for practitioners, and serve as a framework and learning tool for those studying the field. "

    via:bkerr collaboration design-patterns tools social-dynamics

  • [1202.0001] Vector-based model of elastic bonds for DEM simulation of solids

    "A new model for computer simulation of solids, composed of bonded particles, is proposed. Vectors rigidly connected with particles are used for description of deformation of a single bond. The expression for potential energy of the bond and corresponding expressions for forces and moments are proposed. Formulas, connecting parameters of the model with longitudinal, shear, bending and torsional stiffnesses of the bond, are derived. It is shown that the model allows to describe any values of the bond stiffnesses exactly. Two different calibration procedures depending on bond length/thickness ratio are proposed. It is shown that parameters of model can be chosen so that under small deformations the bond is equivalent to either Bernoulli-Euler or Timoshenko rod or short cylinder connecting particles. Simple expressions, connecting parameters of V-model with geometrical and mechanical characteristics of the bond, are derived. Computer simulation of dynamical buckling of the straight discrete rod and discrete half-spherical shell is carried out."

    modeling mechanical-systems materials-science computational-methods algorithms nudge-targets

  • [1202.0253] High-speed Flight in an Ergodic Forest

    "Inspired by birds flying through cluttered environments such as dense forests, this paper studies the theoretical foundations of a novel motion planning problem: high-speed navigation through a randomly-generated obstacle field when only the statistics of the obstacle generating process are known a priori. Resembling a planar forest environment, the obstacle generating process is assumed to determine the locations and sizes of disk-shaped obstacles. When this process is ergodic, and under mild technical conditions on the dynamics of the bird, it is shown that the existence of an infinite collision-free trajectory through the forest exhibits a phase transition. On one hand, if the bird flies faster than a certain critical speed, then, with probability one, there is no infinite collision-free trajectory, i.e., the bird will eventually collide with some tree, almost surely, regardless of the planning algorithm governing the bird's motion. On the other hand, if the bird flies slower than this critical speed, then there exists at least one infinite collision-free trajectory, almost surely. Lower and upper bounds on the critical speed are derived for the special case of a homogeneous Poisson forest considering a simple model for the bird's dynamics. For the same case, an equivalent percolation model is provided. Using this model, the phase diagram is approximated in Monte-Carlo simulations. This paper also establishes novel connections between robot motion planning and statistical physics through ergodic theory and percolation theory, which may be of independent interest."

    robotics planning algorithms nudge-targets

  • [1202.0077] An Interacting Particle Model for Clustering Euclidean Datasets

    "In this paper we propose a method based on interacting particle physics, devised for clustering Euclidean datasets without initial constraints or conditions. We model any dataset as an interacting particle system, whose elements correspond to particles that interact through a simplified version of Lennard-Jones potentials. In so doing, mutual attractive interactions allow to identify groups of proximal particles. The main outcome of this modeling task is an adjacency matrix, taken as input by a community detection algorithm aimed to identify different partitions. The underlying conjecture is that, using a multiresolution analysis, the adopted model allows to find the right number of clusters for any given dataset. Experimental results, performed in comparison with a classical clustering algorithm, confirm this assumption."

    clustering data-analysis algorithms nudge-targets distributed-processing

  • [1201.6583] Empowerment for Continuous Agent-Environment Systems

    "This paper develops generalizations of empowerment to continuous states. Empowerment is a recently introduced information-theoretic quantity motivated by hypotheses about the efficiency of the sensorimotor loop in biological organisms, but also from considerations stemming from curiosity-driven learning. Empowemerment measures, for agent-environment systems with stochastic transitions, how much influence an agent has on its environment, but only that influence that can be sensed by the agent sensors. It is an information-theoretic generalization of joint controllability (influence on environment) and observability (measurement by sensors) of the environment by the agent, both controllability and observability being usually defined in control theory as the dimensionality of the control/observation spaces.…"

    agent-based emergent-design robotics engineering-design machine-learning empowerment nudge

  • [1201.6655] Learning Performance of Prediction Markets with Kelly Bettors

    "In evaluating prediction markets (and other crowd-prediction mechanisms), investigators have repeatedly observed a so-called "wisdom of crowds" effect, which roughly says that the average of participants performs much better than the average participant. The market price—an average or at least aggregate of traders' beliefs—offers a better estimate than most any individual trader's opinion. In this paper, we ask a stronger question: how does the market price compare to the best trader's belief, not just the average trader. We measure the market's worst-case log regret, a notion common in machine learning theory. To arrive at a meaningful answer, we need to assume something about how traders behave. We suppose that every trader optimizes according to the Kelly criteria, a strategy that provably maximizes the compound growth of wealth over an (infinite) sequence of market interactions. We show several consequences.…"

    prediction performance-measure agent-based simulation nudge-targets wisdom-of-crowds

  • Curating the kraken « Public Historian

    'This is why “curate” is still a word to conjure by in our culture.  It still promises transformative power.'

    museology pragmatics naming engineering-of-philosophy

  • [1201.5780] Full and Half Gilbert Tessellations with Rectangular Cells

    "We investigate the ray-length distributions for two different rectangular versions of Gilbert's tessellation. In the full rectangular version, lines extend either horizontally (with east- and west-growing rays) or vertically (north- and south-growing rays) from seed points which form a Poisson point process, each ray stopping when another ray is met. In the half rectangular version, east and south growing rays do not interact with west and north rays. For the half rectangular tessellation we compute analytically, via recursion, a series expansion for the ray-length distribution, whilst for the full rectangular version we develop an accurate simulation technique, based in part on the stopping-set theory of Zuyev, to accomplish the same. We demonstrate the remarkable fact that plots of the two distributions appear to be identical when the intensity of seeds in the half model is twice that in the full model. Our paper explores this coincidence mindful of the fact that, for one model, our results are from a simulation (with inherent sampling error).…"

    geometry tiling algorithms generative-art simulation emergence interesting-problem

Items of some interest:

Posted on by

These are my recent Pinboard.in links:

  • [1201.5604] Discrete and Fuzzy Dynamical Genetic Programming in the XCSF Learning Classifier System

    "A number of representation schemes have been presented for use within Learning Classifier Systems, ranging from binary encodings to neural networks. This paper presents results from an investigation into using discrete and fuzzy dynamical system representations within the XCSF Learning Classifier System. In particular, asynchronous Random Boolean Networks are used to represent the traditional condition-action production system rules in the discrete case and asynchronous Fuzzy Logic Networks in the continuous-valued case. It is shown possible to use self-adaptive, open-ended evolution to design an ensemble of such dynamical systems within XCSF to solve a number of well-known test problems."

    Kauffman-networks learning-classifier-systems genetic-programming nudge-targets interesting

  • [1201.4899] I Like Her more than You: Self-determined Communities

    "In this paper we define what we call an affinity system, which is a set of individuals, each with a vector characterizing its preference for all other individuals in the set. The preference of a member can be given either by a ranking of all members or by a weighted vector that defines the degrees of its affinity to others. Affinity systems are useful for modeling social systems as well as general data sets, as social interactions are often determined by affinities among the members. We also define a natural notion of (potentially overlapping) communities in an affinity system, in which the members of a given community collectively prefer each other to anyone else outside the community. Thus these communities are "self-determined" or "self-certified" by the affinity system. We provide a tight polynomial bound on the number of self-determined communities as a function of the robustness of the community. Moreover, we present a polynomial-time algorithm for enumerating these communities, as well as a local algorithm with a strong stochastic performance guarantee that can find a community in time nearly linear in the of size the community.…"

    network-theory social-capital social-dynamics self-assembly agent-based graph-theory algorithms complexology nudge-targets

  • [1201.5076] Technical Report #SEHIR-IE-VA-12-1: Optimal Obstacle Placement with Disambiguations

    "We introduce the optimal obstacle placement with disambiguations problem wherein the goal is to place true obstacles in an environment cluttered with false obstacles so as to maximize the total traversal length of a navigating agent (NAVA). Prior to the traversal, NAVA is given location information and probabilistic estimates of each disk-shaped hindrance (hereinafter referred to as disk) being a true obstacle. The NAVA can disambiguate a disk's status only when situated on its boundary. There exists an obstacle placing agent (OPA) that locates obstacles prior to NAVA's traversal. The goal of OPA is to place true obstacles in between the clutter in such a way that NAVA's traversal length is maximized in a game-theoretic sense.…"

    agent-based game-theory robotics disambiguation-design nudge-targets military-applications algorithms

  • [1010.5017] Collective motion

    "We review the observations and the basic laws describing the essential aspects of collective motion — being one of the most common and spectacular manifestation of coordinated behavior. Our aim is to provide a balanced discussion of the various facets of this highly multidisciplinary field, including experiments, mathematical methods and models for simulations, so that readers with a variety of background could get both the basics and a broader, more detailed picture of the field. The observations we report on include systems consisting of units ranging from macromolecules through metallic rods and robots to groups of animals and people. Some emphasis is put on models that are simple and realistic enough to reproduce the numerous related observations and are useful for developing concepts for a better understanding of the complexity of systems consisting of many simultaneously moving entities. As such, these models allow the establishing of a few fundamental principles of flocking. In particular, it is demonstrated, that in spite of considerable differences, a number of deep analogies exist between equilibrium statistical physics systems and those made of self-propelled (in most cases living) units. In both cases only a few well defined macroscopic/collective states occur and the transitions between these states follow a similar scenario, involving discontinuity and algebraic divergences."

    emergence emergent-design biology ethology complexology models artificial-life nudge-targets

  • [1201.5568] Dynamic trees for streaming and massive data contexts

    "Data collection at a massive scale is becoming ubiquitous in a wide variety of settings, from vast offline databases to streaming real-time information. Learning algorithms deployed in such contexts must rely on single-pass inference, where the data history is never revisited. In streaming contexts, learning must also be temporally adaptive to remain up-to-date against unforeseen changes in the data generating mechanism. Although rapidly growing, the online Bayesian inference literature remains challenged by massive data and transient, evolving data streams. Non-parametric modelling techniques can prove particularly ill-suited, as the complexity of the model is allowed to increase with the sample size. In this work, we take steps to overcome these challenges by porting standard streaming techniques, like data discarding and downweighting, into a fully Bayesian framework via the use of informative priors and active learning heuristics. We showcase our methods by augmenting a modern non-parametric modelling framework, dynamic trees, and illustrate its performance on a number of practical examples. The end product is a powerful streaming regression and classification tool, whose performance compares favourably to the state-of-the-art."

    data-analysis learning-from-data algorithms drinking-from-the-firehose nudge data-mining

Items of some interest:

Posted on by

These are my recent Pinboard.in links:

  • [1201.5440] Self-assembly of anisotropic soft particles in two dimensions

    "The self assembly of core-corona discs interacting via anisotropic potentials is investigated using Monte Carlo computer simulations. A minimal interaction potential that incorporates anisotropy in a simple way is introduced. It consists in a core-corona architecture in which the center of the core is shifted with respect to the center of the corona. Anisotropy can thus be tuned by progressively shifting the position of the core. Despite its simplicity, the system self organize in a rich variety of structures including stripes, triangular and rectangular lattices, and unusual plastic crystals. Our results indicate that the amount of anisotropy does not alter the lattice spacing and only influences the type of clustering (stripes, micells, etc.) of the individual particles."

    self-assembly biologically-inspired simulation pattern-formation condensed-matter

  • [1201.5477] Entropy-growth-based model of emotionally charged online dialogues

    "We analyze emotionally annotated massive data from IRC (Internet Relay Chat) and model the dialogues between its participants by assuming that the driving force for the discussion is the entropy growth of emotional probability distribution. This process is claimed to be correlated to the emergence of the power-law distribution of the discussion lengths observed in the dialogues. We perform numerical simulations based on the noticed phenomenon obtaining a good agreement with the real data. Finally, we propose a method to artificially prolong the duration of the discussion that relies on the entropy of emotional probability distribution."

    oh-look-power-laws flame-wars social-dynamics complexology cultural-dynamics

  • [1201.4955] Coordination, Differentiation and Fairness in a population of cooperating agents

    "In a recent paper, we analyzed the self-assembly of a complex cooperation network. The network was shown to approach a state, where every agent invests the same amount of resources. Nevertheless, highly-connected agents arise that extract extra-ordinarily high payoffs while contributing comparably little to any of their cooperations. Here, we investigate a variant of the model, in which highly-connected agents have access to additional resources. We study analytically and numerically whether these resources are invested in existing collaborations, leading to a fairer load distribution, or in establishing new collaborations, leading to an even less fair distribution of loads and payoffs."

    collaboration social-capital agent-based network-theory complexology nudge-targets

  • [1201.5426] Constraint Propagation as Information Maximization

    "Dana Scott used the partial order among partial functions for his mathematical model of recursively defined functions. He interpreted the partial order as one of information content. In this paper we elaborate on Scott's suggestion of regarding computation as a process of information maximization by applying it to the solution of constraint satisfaction problems. Here the method of constraint propagation can be interpreted as decreasing uncertainty about the solution — that is, as gain in information about the solution. As illustrative example we choose numerical constraint satisfaction problems to be solved by interval constraints. To facilitate this approach to constraint solving we formulate constraint satisfaction problems as formulas in predicate logic. This necessitates extending the usual semantics for predicate logic so that meaning is assigned not only to sentences but also to formulas with free variables."

    computer-science quite-interesting constraint-processing computational-methods

  • [1201.4459] An efficient parallel algorithm for the longest path problem in meshes

    "In this paper, first we give a sequential linear-time algorithm for the longest path problem in meshes. This algorithm can be considered as an improvement of [13]. Then based on this sequential algorithm, we present a constant-time parallel algorithm for the problem which can be run on every parallel machine."

    algorithms graph-theory computational-complexity nudge-targets

  • [1201.4417] Instabilities and Patterns in Coupled Reaction-Diffusion Layers

    "We study instabilities and pattern formation in reaction-diffusion layers that are diffusively coupled. For two-layer systems of identical two-component reactions, we analyze the stability of homogeneous steady states by exploiting the block symmetric structure of the linear problem. There are eight possible primary bifurcation scenarios, including a Turing-Turing bifurcation that involves two disparate length scales whose ratio may be tuned via the inter-layer coupling. For systems of $n$-component layers and non-identical layers, the linear problem's block form allows approximate decomposition into lower-dimensional linear problems if the coupling is sufficiently weak. As an example, we apply these results to a two-layer Brusselator system. The competing length scales engineered within the linear problem are readily apparent in numerical simulations of the full system. Selecting a $sqrt{2}$:1 length scale ratio produces an unusual steady square pattern."

    cute emergent-design pattern-formation complexology nudge-targets nonlinear-dynamics

  • [1201.4737] Production System Rules as Protein Complexes from Genetic Regulatory Networks

    "This short paper introduces a new way by which to design production system rules. An indirect encoding scheme is presented which views such rules as protein complexes produced by the temporal behaviour of an artificial genetic regulatory network. This initial study begins by using a simple Boolean regulatory network to produce traditional ternary-encoded rules before moving to a fuzzy variant to produce real-valued rules. Competitive performance is shown with related genetic regulatory networks and rule-based systems on benchmark problems."

    evolutionary-algorithms production-systems computer-science emergent-design