This is the experimental HTML rendering of capstract:2610.00009v1. The PDF is the version of record.

Convergent Evolution of Inactive Cable Storage in Electrically Naive Floor Plans

Iria B. Ferrolés
Laboratory for Artificial Morphogenesis
Instituto de Sistemas de Valdema
Vigo
Spain
Johan T. Veldrik
Department of Spatial Computation
Meerhout Institute of Design
Utrecht
Netherlands
Sayuri N. Orikawa
Division of Evolutionary Informatics
Mizunagi College of Engineering
Nagoya
Japan

Abstract—A compartment containing several incompatible cables is usually interpreted as evidence of earlier equipment. We ask whether the same structure can arise in the absence of present or ancestral electrical demand. We evolve the fittings and object assignments of a six-bay workroom used for three manual tasks. Six terminated leads enter as loose articles. The room exposes no port, and every article may be removed at a fixed handling cost. Starting with all leads sent out and all storage open, 42 of 48 lineages evolved a closed drawer holding at least five leads and no working tool. An exact cost calculation places five leads in bay 2 and leaves the sixth on the surface in bay 4. Thirty-seven lineages found this arrangement. Flattening the exposed footprint of a lead to that of a tool abolished drawer formation at the same removal price. The result places a limit on functional reconstruction from inventories. Even the drawer whose contents are one lead short of complete can be accounted for without an appliance.

Index Terms—evolutionary design, phenotypic convergence, spatial allocation, artifact inventories

IIntroduction

A surveyor finds three work surfaces and a shallow drawer. The surfaces hold a brush, a rule, and a hand stamp. In the drawer are five leads with molded plugs at either end. An obvious reconstruction places a device at one of the surfaces and dates the surviving leads to the interval between its installation and removal. The reconstruction has the advantage of assigning a purpose to nearly everything in the room. It also makes a claim about a device for which the surveyor has no other evidence.

There is a second possibility. Long loose objects occupy scarce surface area. Once one of them has justified the expense of enclosing a bay, the price of adding a second is quite low. The last article to enter such a bay may have less in common with the first than either has with an article which spent the entire occupation period outdoors. This account makes a different prediction about the surviving inventory. A useful tool should be less likely to accompany the leads than an equally bulky object that nobody has any reason to retrieve.

Testing these accounts on extant workshops would require an unusually complete history of the site. In particular, a tenancy that begins without power does not establish that the previous tenant lacked power. We use artificial descent with a known founder. The founder has three working tools and sends every loose lead to an external collection point. There are no electrical operations in the task language, no receptacles in the room, and no earlier population. We record whether independent searches starting here build a drawer for the cables. The parts themselves have to be supplied. Our question concerns the evolutionary origin of the collection, including the work of putting the parts together, rather than the origin of its individual members.

ARelated experiments

Evolutionary design has a practical advantage for this question. Both the formal description of an artifact and the process by which the artifact came about are accessible to the observer. Sims evolved articulated bodies and controllers jointly [1]. Lipson and Pollack carried the resulting line of inquiry into fabrication [2]. Designs obtained under such procedures often give quite good evidence of their evaluation environment. The converse inference is more difficult. Clune and colleagues obtained network modules by charging for connections [3]. Given the modules alone, a charge for connections would have been only one of several possible explanations. The distinction between what a structure does now and the history of its acquisition is familiar from the terminology of Gould and Vrba [4].

For allocations in physical space we follow Kirsh’s treatment of the cost of leaving a task environment in a particular arrangement [5]. A long lead left across a bench imposes some charge on the next use of that bench even if its owner never connects it. Previous inventory reconstructions have represented unused leads by the terminals to which they might have belonged [6], [7]. That coding would be inconvenient here. Our world has a complete parts catalogue and an empty catalogue of terminals. A separate line of work charges for access to a berth and for the objects between the hand and the berth [8], [9]. We retain a cost for co-occupancy and explicitly price the alternative of sending an item away.

Indirect encodings can make repeated or symmetric fittings likely before selection begins [10]. We use individual bits for the enclosed bays and separate alleles for the destinations of superficially identical leads. Consequently a mutation can place two cables side by side only by changing one or both destinations. We do not reward that event or maintain an archive of unusual plans. The performance criterion and an archive of outcomes would give different sampling distributions [11]. Here a repeated outcome of an ordinary performance search is the object of measurement.

IIThe workroom

Consider a row of six adjacent bays numbered 0 to 5 from the west end. The distance between successive bays defines one unit of handling effort. A tool fetched from a bay and later returned incurs both legs of the trip. There is a brush station at 0, a rule station at 3, and a stamp station at 5. In one occupation period the brush is called for seven times, the rule five times and the stamp eight times. An occupation period is an accounting interval of fixed workload. Increasing its duration without changing the number of jobs leaves all charges unchanged.

Six leads enter singly at bays 1, 2, 2, 3, 3, and 4. The arrival coordinates are part of the instance. The leads can be identified individually at intake, including the pairs that enter at the same coordinate. Each has a different catalogue entry giving its two connector faces. A face fits nothing on the task list. There is no residual value at the end of the occupation period. The model therefore admits a literal test of a claim that is difficult to assess from a household inventory, namely that a lead has been retained exclusively for an appliance which the household does not own and has never owned. We give the word inactive the narrower meaning of zero calls during the entire history of the task.

Each bay has a surface. A builder may replace it with a drawer, at a fixed charge of 5 per period which includes the use of the runner and face. Once enclosed, a bay holds the same number of articles as before. The face cannot selectively conceal some of its contents. Opening it to put away an arriving lead costs 0.50. Fetching and returning a tool to a drawer costs an additional 0.75 per request, including the return. These values represent complete movements. The latter charge need not equal twice the former because the drawer may be left open during an individual job. Different jobs are separated by an interval in which it is shut.

Let be the face bit, the number of tools in bay , the number of leads, and . Write for the sum of the request counts for the tools assigned there. If denotes the home of tool , its station and its request count, its transport charge is . Arrival can be assigned to a bay or to external collection, denoted by . With intake coordinate , the one-way charge is

The external service accepts any number of articles. It takes the same handling effort to surrender an article at any of the six intake coordinates. Batching articles for collection would change this rule. A fixed charge for a visit to collect the entire box can be considerably smaller than six separate charges, and we study the price per article directly in Section IV.

We minimize the following cost, expressed in bay steps per occupation period. A face installed on an empty bay is chargeable.

Here is the positive part. The exposed footprint coefficient applies to a loose lead over the whole period. An enclosed lead remains in the inventory but occupies no work surface. A compact tool on the surface incurs 0.45. Search among the articles sharing a bay costs 0.20 per other article on each retrieval, whether the bay has a face or not. These terms distinguish two quite different uses of space. Two loose leads on a surface take up space even if neither is ever sought. Two items in a drawer slow the hand only when one of them is sought. A drawer can be filled with six objects without ever incurring this latter charge. Overfilling costs 20 per excess article to allow evaluation of every mutant without a repair step.

The constants in Eq. (2) specify a constructed environment. They are not timings taken from a particular kitchen. In the reference setting , a nominal five-step trip saves the full future cost of accommodating one arrival. This makes the founder feasible and gives an upper bound of on the cost of any selected descendant. A plan can improve immediately by saving a short trip. It takes more than one such improvement for the installation charge to pay. This separation is why comparing the finished plan with an empty, unequipped workroom would be an inadequate experiment.

IIIDescent and scoring

The genotype has fifteen loci. The first six are binary. Three six-valued loci locate the working tools, and six seven-valued loci allocate the incoming articles. In the founder all face bits are zero, the tools are at their stations, and the allocation vector is . An equal probability per locus gives an expected one substitution per offspring. A substitution chooses uniformly from the other legal values at that locus. It can therefore move a cable from the west end to the east end in one generation. We charge for handling in the developed plan, without charging for remodeling the founder’s actual furnishings.

We used a discrete evolution strategy without crossover. All six offspring are copied from the same parent at the beginning of each generation [12], [13]. The lowest cost among parent and offspring survives. A tied parent stays and a tie between improving siblings goes to the first drawn. This rule prevents the retrospective identification of an unselected transition as an improvement. It also makes entry into some basins harder than it would be with a random walk on ties. We examine the size of the effect of allowing several substitutions in one birth. The difference between representation and selection has long been a concern in genetic search [14], [15]. In this small problem it can also be checked by finding an exact minimum.

We ran 48 mutation streams for 600 generations per condition. The deadline was fixed in units of offspring evaluation, with a budget of 3,600 per stream plus the scoring of its founder. Exactly the same initial plan and seed list were used in each condition. The published proportions are frequencies over streams on this floor. The binomial score interval [16] gives their Monte Carlo precision if the streams are regarded as independent replicates. It does not include uncertainty in the price of a drawer. A reference implementation can enumerate this instance without estimating a fitness from samples, so the uncertainty in a fitness value reported below is zero to the precision of the cost table.

For the primary endpoint we count a terminal plan when a single enclosed bay contains five or more leads and no working tools. Six leads distributed over two faces do not suffice. We chose five to allow one lead to remain out for reasons other than electrical service. We also give counts at cutoffs of four and six. On this floor at most one bay can meet the primary endpoint. The person reading the inventory needs only the face positions and the disposition of nine objects. The parent identifier and the value of Eq. (2) can be concealed. This is stricter than counting repeated construction of a shallow drawer, since a drawer devoted to the working stamp could have arisen in a workshop with no supply of cables.

Three comparisons use the same encoding. With compact articles, each lead charges 0.45 on the open bench, its intake and its terminal identifications being unchanged. Cheap collection sets while retaining the original footprint. Under neutral descent the first of the six offspring replaces the parent regardless of its cost. The other five are scored and discarded so the evaluation budgets match. Neutral descent is informative here because a binary face is rather easy to assemble by chance. Orientation of six independent destinations toward that face is a different matter. We also run a selected process with exactly one uniformly chosen locus substituted in each offspring, including offspring of parents at a strict local minimum.

IVResults

The five-lead drawer occurred in 42 of 48 selected lineages at the reference prices, a frequency of 0.875 (95% interval 0.753 to 0.941). None appeared at generation zero. The corresponding numbers at generations 40, 100 and 250 were 5, 24 and 37. The points in Fig. 1 are repeated observations of the same lineages. They are not successive cohorts. A lineage that constructs a drawer can lose it, or empty part of it, while continuing to lower its total cost. We observed 43 distinct lineages with at least one qualifying plan and 42 with one at the final census. Among those that ever met the endpoint, the median first occurrence was at generation 82. This conditional time omits five censored runs.

0102030400200400600GenerationLineages with drawerCost selectionNeutral descent
Fig. 1. Current qualifying parent at selected generations. Each count is out of 48 lineages.

Eight neutral lineages happened upon the arrangement between censuses and subsequently lost it. Selecting the most suggestive plan from each lineage history would thus have supported an appreciably different reading of the neutral experiment. The terminal comparison in Table I uses arbitrary fixed duration for both conditions. Its advantage over selection of a fossil from the archive is simply that the investigator has no opportunity to decide how long to excavate.

TABLE I
Terminal plan counts and costs after 3,600 offspring per founder. A qualifying drawer is tool-free. Cost includes external collection at the price used in that row.
Condition Lineages Qualifying Median cost Cost range
Reference 48 42 14.10 14.10 to 17.10
Compact articles 48 0 6.05 6.05 to 6.05
Cheap collection 48 0 7.35 7.35 to 7.35
Neutral descent 48 0 143.83 67.45 to 204.25

The compact and cheap-collection controls agree at the binary endpoint. Their inventories have little else in common. In the cheap condition each of the six articles still goes out for collection. A compact article is economical to leave exposed, and the compact plans attain their lower costs by bringing the articles in. In both cases a zero count out of 48 has a score upper limit of 0.074. Scores in different rows of Table I price the same movements differently. In particular, the small number 6.05 cannot be substituted for a competitive score in the reference room.

The first single-locus change of a face always alters the expression of every assignment to the altered bay. Separate destination loci alone do not eliminate this source of linkage at the phenotypic level. With exactly one substitution per child, 33 of 48 reference lineages produced a qualifying parent, of which 29 reached cost 14.10. A search need not move several arrivals in a single mutation to enclose them together. Some of the earlier selected substitutions have already gathered the arrivals loosely on the surface. Closing the face over three idle leads at rest saves even if no subsequent arrival is diverted. With only two present, it loses 1.50. A closed and wholly empty bay loses the entire installation fee.

AContents of the best plan

In 37 of the 42 qualifying inventories the drawer is at bay 2. All five remaining qualifying inventories put it at bay 1. The reference run reaches the certified minimum in the former case (Section IV.B). The objects that entered at bays 1, 2, 2, 3 and 3 go to the drawer. The sixth lead lies by itself at bay 4. A shift in the occupancy cutoff from five articles to four admits no additional lineages. Reducing it to three admits five. At the six-article cutoff no lineage qualifies. None of these five-lead drawers was too small for the cable left outside.

The calculation for the sixth article is local. Its cost on the open surface where it arrived is 2.25. Carrying it two bays west and opening a face already paid for costs 2.50. Sending it for collection costs 5. The marginal charge of 0.25 for completing the collection is enough for strict selection to leave the sixth cable lying out. A survey that sampled only the drawer would therefore miss the component for which no move had been justified. The five inside incur no search charge. A request for even one would introduce a cost for all four of its neighbors.

We varied the lead footprint and per-item collection price in Eq. (1) while keeping all other coefficients fixed. Each cell in Fig. 2 contains 48 searches. At , increasing from 2 to 3 raised the number of drawers from zero to eight. At we saw 39, close to the reference result. The response at the higher footprint was less regular. In particular, when and , a lone occupant on an open surface costs more than the collector, even if it arrived at precisely that bay. Several arrivals may together make enclosure economical. A policy of accepting successive strict improvements starting with all six sent out has difficulty reaching that state. This accounts for a low-frequency region in a sweep that might otherwise be taken for a change in the optimum itself.

000000000000008394241000424141h = 0.45h = 1.35h = 2.25h = 3.15R = 123456010203040Lineages
Fig. 2. Number of qualifying parents per 48 lineages at each combination of handling charges. Each charge is measured in bay steps per article per period.

BConditional and exact optima

The observed mixture of drawer positions could reflect genuine degeneracy of the optimum or incomplete search. We distinguished these possibilities by minimizing Eq. (2) independently of the runs. Location-allocation methods often enumerate candidate sites before assigning customers [17], [18]. Here a berth occupied by a tool changes the marginal cost of assigning an arriving lead to it. Enumerating the tool positions first removes this dependence. For larger rooms the remaining assignment can be handled with capacitated flow methods [19]. Direct enumeration is cheaper to audit at this scale.

We can discard many cases without enumeration at all. A displaced tool costs at least 10 for travel. If any drawer is installed, even ignoring every deposit charge this gives at least 15, already above 14.10. If no drawer is installed, each lead either occupies exposed area or is collected, at a cost of at least 2.25. Thus a displaced tool cannot be part of an optimal plan. With all tools at their stations the minimum combined charge on tools for exposure or opening the drawer is 1.35, since even the least frequently requested tool would incur in an enclosed bay. Two or more drawers therefore cost at least , because each lead incurs at least half a step. The case of zero or one drawer remains.

For each case in Table II we enumerated the assignments in intake order. No randomized optimizer was used for this calculation. The reference plan lies between two more expensive alternatives which put one or more arrivals closer to where they entered. Putting the drawer at 3, where two leads entered, would require keeping the rule behind it or paying for the rule’s travel. There are five requests for the rule and no requests for the leads. Once all the candidates with displaced rules are excluded by the lower bound, the computation at 3 is straightforward.

TABLE II
Exact minimum cost at the reference prices for each single face with tools at their stations. Also shown is the unrestricted open-surface minimum with the same tool assignments.
Face at bay Minimum cost
None 16.85
0 26.65
1 17.10
2 14.10
3 21.65
4 16.60
5 27.40

The case analysis certifies 14.10 globally. The best open plan does better than the best plan with a drawer at 1. Our endpoint nevertheless includes five lineages in the latter class. Frequency of enclosure is an imperfect measure of design quality even on the floor that selects for it. In the terminal cost distribution (Fig. 3), the run at 16.85 is the one for which an observer would find no face to open. Five runs at 16.60 split the leads more evenly between exposed and enclosed storage. A longer run might move these populations to the same final arrangement, but their present dispositions follow from the declared search budget and do not require any assumption about what would eventually fix.

0510152025303514.1016.6016.8517.10Terminal cost (bay steps per period)Lineages
Fig. 3. Terminal counts on the reference floor by attained cost. Categories are the four observed cost values in bay steps per period.

VFunctional interpretation

In evolutionary studies an object of known construction can be presented to an observer whose task is to recover the sequence of environments in which it arose [20]. The observer is usually given some way to distinguish old environmental demands from current ones. We used the strongest available intervention on past demand, namely deletion of electrical operations from the entire history of the lineage. This deletion did nothing to the outlines of the objects or the cost of putting them somewhere. A storage arrangement that would have served as evidence of a removed appliance still arose under the intervention.

The drawer has a current function. It lets long objects remain in the room without spreading over its working surfaces. That function can be selected even when the contents have no function individually. It is tempting to attribute an option value to keeping an incompatible lead against the arrival of compatible equipment. There is no such term in Eq. (2). Removing the intake charge for collection largely removes the reason to keep the articles in the first place. Charging for their future retrieval, if any, would require specifying where the appliance would be and which lead it would call for. The location prediction would then depend on a job absent from the present experiment.

A single drawer in a room cannot be evidence for common descent among multiple rooms. In this instance even agreement on the bay number is weak evidence. Objects and station coordinates are inherited as environmental conditions in every replicate. Almost all the work of locating the successful drawer can be done by an observer who knows where things enter and where the working rule is kept. A survey intended to detect transmission of a floor plan should record these coordinates before comparing drawer positions. The experiment gives no estimate of how variable such coordinates actually are.

There are other limitations material to the inverse problem. The genome cannot build a cable hook, install a second store behind the first, or send a whole box for collection at the price of one article. Enlarging the vocabulary of furnishings might produce the same congregation of leads in a container that an observer would call something other than a drawer. The leads do not knot. Charging for pairwise entanglement even with zero retrieval would penalize aggregation on its own and could support several smaller compartments. Adding a price only when one of the tangled leads is pulled would leave the five idle articles undisturbed. The distinction matters when transferring the model to a place where drawers are occasionally emptied for inspection.

The fixed number of arrivals also bounds the claim. This is a one-period organization inherited and evaluated repeatedly with fresh inventory. It does not predict that indefinitely many deliveries can go in one shallow drawer. Every genome specifies a disposition for each of six arrivals. If a building supervisor finds four more types than the task list allowed, the missing four could provide evidence about a different supply or an earlier task. Our construction accounts for a distribution of objects already delivered; it cannot account for their delivery. What can be dispensed with is the intermediate appliance customarily placed between the delivery of the cable and its deposition in the drawer.

AReconstruction of the runs

The input in Table III gives the complete allocation instance in addition to the coefficients in Eq. (2). A lead is counted once regardless of how many ends it has. Coincident arrivals carry separate destination alleles. It suffices to keep two counters for each berth, one for number of articles and one for the accumulated request count. In the compact treatment only the exposed-area coefficient changes. In particular a compact article placed with the rule incurs exactly the same search charge per request as a lead placed with it.

TABLE III
Inventory and job ledger. The bay column gives the source of an incoming article or the point of use of a working tool.
Inventory entry Bay Requests
Brush 0 7
Rule 3 5
Stamp 5 8
Leads A, B, C 1, 2, 2 0 each
Leads D, E, F 3, 3, 4 0 each

For replicate , initialize unsigned state to . At each draw set to and return . For each offspring visit loci in the order specified in Section III, drawing once at each locus for the test . If it passes, draw another uniform variate and add modulo to the old value, where is the alphabet size. Bay indices begin with zero and external collection has code 6. For the single-substitution comparison draw the locus as before drawing its replacement. The stream advances on non-improving offspring as well. These details matter more to an exact replay than the order of summation of the terms, provided the latter are scored in hundredths of a step.

A minimal score check is the assignment with only bay 2 enclosed and tools at their stations. Its face charge is 5, walking with incoming leads costs 3, and opening on intake costs 2.50. Exposure costs 1.35 for the tools plus 2.25 for the lead at bay 4. There are no other charges. With the face removed and all locations fixed the score becomes 17.85. Reoptimizing the six assignments with the face absent saves one additional step, which explains the difference between this deletion experiment and the open row of Table II. Deleting an unused cable from the primary drawer saves a different amount again, depending on the intake site. These interventions answer distinct questions despite leaving rooms that look alike when the drawers are closed.

Acknowledgments

We thank the Valdema workshop staff for drawing separate intake and point-of-use plans.

References

  1. [1]K. Sims, “Evolving virtual creatures,” in Proc. SIGGRAPH, 1994, pp. 15–22.
  2. [2]H. Lipson and J. B. Pollack, “Automatic design and manufacture of robotic lifeforms,” Nature, vol. 406, pp. 974–978, 2000.
  3. [3]J. Clune, J.-B. Mouret, and H. Lipson, “The evolutionary origins of modularity,” Proceedings of the Royal Society B, vol. 280, pp. 20122863, 2013.
  4. [4]S. J. Gould and E. S. Vrba, “Exaptation: A missing term in the science of form,” Paleobiology, vol. 8, pp. 4–15, 1982.
  5. [5]D. Kirsh, “The intelligent use of space,” Artificial Intelligence, vol. 73, pp. 31–68, 1995.
  6. [6]M. F. Ardelin and E. J. Keskava, “Terminal inventories as evidence of absent workshop equipment,” Studies in Artifact Reconstruction, vol. 12, pp. 44–62, 2018.
  7. [7]L. T. Renfald, “Coding paired interfaces in secondary deposits of workshop material,” Quarterly of Spatial Assemblages, vol. 7, pp. 203–217, 2020.
  8. [8]N. O. Gessari and A. F. Lozera, “Charging for displacement in small work surfaces,” Transactions on Spatial Task Models, vol. 9, pp. 28–41, 2021.
  9. [9]E. H. Suzel, “Retrieval penalties in shared manual storage,” Journal of Situated Allocation, vol. 15, pp. 66–84, 2023.
  10. [10]K. O. Stanley, “Compositional pattern producing networks: A novel abstraction of development,” Genetic Programming and Evolvable Machines, vol. 8, pp. 131–162, 2007.
  11. [11]J. Lehman and K. O. Stanley, “Abandoning objectives: Evolution through the search for novelty alone,” Evolutionary Computation, vol. 19, pp. 189–223, 2011.
  12. [12]H.-G. Beyer and H.-P. Schwefel, “Evolution strategies: A comprehensive introduction,” Natural Computing, vol. 1, pp. 3–52, 2002.
  13. [13]A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing. Springer, 2015.
  14. [14]J. H. Holland, Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.
  15. [15]D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989.
  16. [16]E. B. Wilson, “Probable inference, the law of succession, and statistical inference,” Journal of the American Statistical Association, vol. 22, pp. 209–212, 1927.
  17. [17]S. L. Hakimi, “Optimum locations of switching centers and the absolute centers and medians of a graph,” Operations Research, vol. 12, pp. 450–459, 1964.
  18. [18]M. S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications. Wiley, 1995.
  19. [19]R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
  20. [20]E. M. Valterin and J. H. Corfald, “Reconstructing task histories from the geometry of evolved fixtures,” Annals of Computational Artifacts, vol. 4, pp. 85–102, 2019.