Solving the shepherding problem: heuristics for herding autonomous, interacting agents.
Ontology highlight
ABSTRACT:
SUBMITTER: Strombom D
PROVIDER: S-EPMC4191104 | biostudies-literature | 2014 Nov
REPOSITORIES: biostudies-literature
Publications
Solving the shepherding problem: heuristics for herding autonomous, interacting agents.
Strömbom Daniel D Mann Richard P RP Wilson Alan M AM Hailes Stephen S Morton A Jennifer AJ Sumpter David J T DJ King Andrew J AJ
Journal of the Royal Society, Interface 20141101 100
Herding of sheep by dogs is a powerful example of one individual causing many unwilling individuals to move in the same direction. Similar phenomena are central to crowd control, cleaning the environment and other engineering problems. Despite single dogs solving this 'shepherding problem' every day, it remains unknown which algorithm they employ or whether a general algorithm exists for shepherding. Here, we demonstrate such an algorithm, based on adaptive switching between collecting the agent ...[more]
Similar Datasets
Project description:BackgroundThe study of genome rearrangements has become a mainstay of phylogenetics and comparative genomics. Fundamental in such a study is the median problem: given three genomes find a fourth that minimizes the sum of the evolutionary distances between itself and the given three. Many exact algorithms and heuristics have been developed for the inversion median problem, of which the best known is MGR.ResultsWe present a unifying framework for median heuristics, which enables us to clarify existing strategies and to place them in a partial ordering. Analysis of this framework leads to a new insight: the best strategies continue to refer to the input data rather than reducing the problem to smaller instances. Using this insight, we develop a new heuristic for inversion medians that uses input data to the end of its computation and leverages our previous work with DCJ medians. Finally, we present the results of extensive experimentation showing that our new heuristic outperforms all others in accuracy and, especially, in running time: the heuristic typically returns solutions within 1% of optimal and runs in seconds to minutes even on genomes with 25'000 genes--in contrast, MGR can take days on instances of 200 genes and cannot be used beyond 1'000 genes.ConclusionFinding good rearrangement medians, in particular inversion medians, had long been regarded as the computational bottleneck in whole-genome studies. Our new heuristic for inversion medians, ASM, which dominates all others in our framework, puts that issue to rest by providing near-optimal solutions within seconds to minutes on even the largest genomes.
| S-EPMC3009502 | biostudies-literature
Project description:Diet induces parallel changes to the gut microbiota and problem solving performance in a wild bird
| PRJEB40949 | ENA
Project description:In this paper we argue that a synthesis of findings across the various sub-areas of research in complex problem solving and consequently progress in theory building is hampered by an insufficient differentiation of complexity and difficulty. In the proposed framework of person, task, and situation (PTS), complexity is conceptualized as a quality that is determined by the cognitive demands that the characteristics of the task and the situation impose. Difficulty represents the quantifiable level of a person's success in dealing with such demands. We use the well-documented "semantic effect" as an exemplar for testing some of the conceptual assumptions derived from the PTS framework. We demonstrate how a differentiation between complexity and difficulty can help take beyond a potentially too narrowly defined psychometric perspective and subsequently gain a better understanding of the cognitive mechanisms behind this effect. In an empirical study a total of 240 university students were randomly allocated to one of four conditions. The four conditions resulted from contrasting the semanticity level of the variable labels used in the CPS system (high vs. low) and two instruction conditions for how to explore the CPS system's causal structure (starting with the assumption that all relationships between variables existed vs. starting with the assumption that none of the relationships existed). The variation in the instruction aimed at inducing knowledge acquisition processes of either (1) systematic elimination of presumptions, or (2) systematic compilation of a mental representation of the causal structure underpinning the system. Results indicate that (a) it is more complex to adopt a "blank slate" perspective under high semanticity as it requires processes of inhibiting prior assumptions, and (b) it seems more difficult to employ a systematic heuristic when testing against presumptions. In combination, situational characteristics, such as the semanticity of variable labels, have the potential to trigger qualitatively different tasks. Failing to differentiate between 'task' and 'situation' as independent sources of complexity and treating complexity and difficulty synonymously threaten the validity of performance scores obtained in CPS research.
| S-EPMC5641385 | biostudies-other
Project description:According to the restructuring hypothesis, insight problem solving typically progresses through consecutive stages of search, impasse, insight, and search again for someone, who solves the task. The order of these stages was determined through self-reports of problem solvers and has never been verified behaviorally. We asked whether individual analysis of problem solving attempts of participants revealed the same order of problem solving stages as defined by the theory and whether their subjective feelings corresponded to the problem solving stages they were in. Our participants tried to solve the Five-Square problem in an online task, while we recorded the time and trajectory of their stick movements. After the task they were asked about their feelings related to insight and some of them also had the possibility of reporting impasse while working on the task. We found that the majority of participants did not follow the classic four-stage model of insight, but had more complex sequences of problem solving stages, with search and impasse recurring several times. This means that the classic four-stage model is not sufficient to describe variability on the individual level. We revised the classic model and we provide a new model that can generate all sequences found. Solvers reported insight more often than non-solvers and non-solvers reported impasse more often than solvers, as expected; but participants did not report impasse more often during behaviorally defined impasse stages than during other stages. This shows that impasse reports might be unreliable indicators of impasse. Our study highlights the importance of individual analysis of problem solving behavior to verify insight theory.
| S-EPMC4523725 | biostudies-literature
Project description:When confronted with novel problems, problem-solvers must decide whether to copy a modeled solution or to explore their own unique solutions. While past work has established that infants can learn to solve problems both through their own exploration and through imitation, little work has explored the factors that influence which of these approaches infants select to solve a given problem. Moreover, past work has treated imitation and exploration as qualitatively distinct, although these two possibilities may exist along a continuum. Here, we apply a program novel to developmental psychology (DeepLabCut) to archival data (Lucca et al., 2020) to investigate the influence of the effort and success of an adult's modeled solution, and infants' firsthand experience with failure, on infants' imitative versus exploratory problem-solving approaches. Our results reveal that tendencies toward exploration are relatively immune to the information from the adult model, but that exploration generally increased in response to firsthand experience with failure. In addition, we found that increases in maximum force and decreases in trying time were associated with greater exploration, and that exploration subsequently predicted problem-solving success on a new iteration of the task. Thus, our results demonstrate that infants increase exploration in response to failure and that exploration may operate in a larger motivational framework with force, trying time, and expectations of task success.
| S-EPMC8606407 | biostudies-literature
Project description:Behavioural innovations with tool-like objects in non-habitually tool-using species are thought to require complex physical understanding, but the underlying cognitive processes remain poorly understood. A few parrot species are capable of innovating tool-use and borderline tool-use behaviours. We tested this capacity in two species of macaw (Ara ambiguus, n = 9; Ara glaucogularis, n = 8) to investigate if they could solve a problem-solving task through manufacture of a multi-stone construction. Specifically, after having functional experience with a pre-inserted stick tool to push a reward out of a horizontal tube, the subjects were required to insert five stones consecutively from one side to perform the same function as the stick tool with the resulting multi-component construction. One Ara glaucogularis solved the task and innovated the stone construction after the experience with the stick tool. Two more subjects (one of each species) did so after having further functional experience of a single stone pushing a reward out of a shortened tube. These subjects were able to consistently solve the task, but often made errors, for example counter-productive stone insertions from the opposing end, even in some of the successful trials. Conversely, multiple trials without errors also suggested a strong goal direction. Their performance in the follow-up tasks was inconclusive since they sometimes inserted stones into un-baited or blocked 'dummy tubes', but this could have been an attention-deficit behaviour as subjects had not encountered these 'dummy tubes' before. Overall, the successful subjects' performance was so erratic that it proved difficult to conclude whether they had functional understanding of their multi-stone constructions.
| S-EPMC7979646 | biostudies-literature
Project description:Accumulating neuroscience evidence indicates that human intelligence is supported by a distributed network of frontal and parietal regions that enable complex, goal-directed behaviour. However, the contributions of this network to social aspects of intellectual function remain to be well characterized. Here, we report a human lesion study (n = 144) that investigates the neural bases of social problem solving (measured by the Everyday Problem Solving Inventory) and examine the degree to which individual differences in performance are predicted by a broad spectrum of psychological variables, including psychometric intelligence (measured by the Wechsler Adult Intelligence Scale), emotional intelligence (measured by the Mayer, Salovey, Caruso Emotional Intelligence Test), and personality traits (measured by the Neuroticism-Extraversion-Openness Personality Inventory). Scores for each variable were obtained, followed by voxel-based lesion-symptom mapping. Stepwise regression analyses revealed that working memory, processing speed, and emotional intelligence predict individual differences in everyday problem solving. A targeted analysis of specific everyday problem solving domains (involving friends, home management, consumerism, work, information management, and family) revealed psychological variables that selectively contribute to each. Lesion mapping results indicated that social problem solving, psychometric intelligence, and emotional intelligence are supported by a shared network of frontal, temporal, and parietal regions, including white matter association tracts that bind these areas into a coordinated system. The results support an integrative framework for understanding social intelligence and make specific recommendations for the application of the Everyday Problem Solving Inventory to the study of social problem solving in health and disease.
| S-EPMC4163035 | biostudies-literature
Project description:Cognitive flexibility allows individuals to adapt to novel situations. However, this ability appears to develop slowly over the first few years of life, mediated by task complexity and opacity. We used a physically simple novel task, previously tested with nonhuman primates, to explore the development of flexible problem solving in 2-, 3-, and 4-year-old children from a developmental and comparative perspective. The task goal was to remove barriers (straws) from a clear tube to release a ball. The location of the ball, and therefore the number of straws necessary to retrieve it, varied across two test phases (four of five straws and two of five straws, respectively). In Test Phase 1, all children retrieved the ball in Trial 1 and 83.61% used the most efficient method (removing only straws below the ball). Across Phase 1 trials, 4-year-olds were significantly more efficient than 2-year-olds, and solve latency decreased for all age groups. Test Phase 2 altered the location of the ball, allowing us to explore whether children could flexibly adopt a more efficient solution when their original (now inefficient) solution remained available. In Phase 2, significantly more 4-year-olds than 2-year-olds were efficient; the older children showed greater competency with the task and were more flexible to changing task demands than the younger children. Interestingly, no age group was as flexible in Phase 2 as previously tested nonhuman primates, potentially related to their relatively reduced task exploration in Phase 1. Therefore, this causally clear task revealed changes in cognitive flexibility across both early childhood and species.
| S-EPMC7449664 | biostudies-literature
Project description:Despite great strides in both machine learning and neuroscience, we do not know how the human brain solves problems in the general sense. We approach this question by drawing on the framework of engineering control theory. We demonstrate a computational neural model with only localist learning laws that is able to find solutions to arbitrary problems. The model and humans perform a multi-step task with arbitrary and changing starting and desired ending states. Using a combination of computational neural modeling, human fMRI, and representational similarity analysis, we show here that the roles of a number of brain regions can be reinterpreted as interacting mechanisms of a control theoretic system. The results suggest a new set of functional perspectives on the orbitofrontal cortex, hippocampus, basal ganglia, anterior temporal lobe, lateral prefrontal cortex, and visual cortex, as well as a new path toward artificial general intelligence.
| S-EPMC9883268 | biostudies-literature
Project description:Biological sequences are composed of long strings of alphabetic letters rather than arrays of numerical values. Lack of a natural underlying metric for comparing such alphabetic data significantly inhibits sophisticated statistical analyses of sequences, modeling structural and functional aspects of proteins, and related problems. Herein, we use multivariate statistical analyses on almost 500 amino acid attributes to produce a small set of highly interpretable numeric patterns of amino acid variability. These high-dimensional attribute data are summarized by five multidimensional patterns of attribute covariation that reflect polarity, secondary structure, molecular volume, codon diversity, and electrostatic charge. Numerical scores for each amino acid then transform amino acid sequences for statistical analyses. Relationships between transformed data and amino acid substitution matrices show significant associations for polarity and codon diversity scores. Transformed alphabetic data are used in analysis of variance and discriminant analysis to study DNA binding in the basic helix-loop-helix proteins. The transformed scores offer a general solution for analyzing a wide variety of sequence analysis problems.
| S-EPMC1088356 | biostudies-other