Distributed sequential task allocation in foraging swarms

When designing a practical swarm robotics system, self-organized task allocation is key to make best use of resources. Current research in this area focuses on task allocation which is either distributed (tasks must be performed at different locations) or sequential (tasks are complex and must be split into simpler sub-tasks and processed in order). In practice, however, swarms will need to deal with tasks which are both distributed and sequential. In this paper, a classic foraging problem is extended to incorporate both distributed and sequential tasks. The problem is analysed theoretically, absolute limits on performance are derived, and a set of conditions for a successful algorithm are established. It is shown empirically that an algorithm which meets these conditions, by causing emergent cooperation between robots can achieve consistently high performance under a wide range of settings without the need for communication. © 2013 IEEE.

Supporting intra-task parallelism in real-time multiprocessor systems

Os sistemas de tempo real modernos geram, cada vez mais, cargas computacionais pesadas e dinâmicas, começando-se a tornar pouco expectável que sejam implementados em sistemas uniprocessador. Na verdade, a mudança de sistemas com um único processador para sistemas multi- processador pode ser vista, tanto no domínio geral, como no de sistemas embebidos, como uma forma eficiente, em termos energéticos, de melhorar a performance das aplicações. Simultaneamente, a proliferação das plataformas multi-processador transformaram a programação paralela num tópico de elevado interesse, levando o paralelismo dinâmico a ganhar rapidamente popularidade como um modelo de programação. A ideia, por detrás deste modelo, é encorajar os programadores a exporem todas as oportunidades de paralelismo através da simples indicação de potenciais regiões paralelas dentro das aplicações. Todas estas anotações são encaradas pelo sistema unicamente como sugestões, podendo estas serem ignoradas e substituídas, por construtores sequenciais equivalentes, pela própria linguagem. Assim, o modo como a computação é na realidade subdividida, e mapeada nos vários processadores, é da responsabilidade do compilador e do sistema computacional subjacente. Ao retirar este fardo do programador, a complexidade da programação é consideravelmente reduzida, o que normalmente se traduz num aumento de produtividade. Todavia, se o mecanismo de escalonamento subjacente não for simples e rápido, de modo a manter o overhead geral em níveis reduzidos, os benefícios da geração de um paralelismo com uma granularidade tão fina serão meramente hipotéticos. Nesta perspetiva de escalonamento, os algoritmos que empregam uma política de workstealing são cada vez mais populares, com uma eficiência comprovada em termos de tempo, espaço e necessidades de comunicação. Contudo, estes algoritmos não contemplam restrições temporais, nem outra qualquer forma de atribuição de prioridades às tarefas, o que impossibilita que sejam diretamente aplicados a sistemas de tempo real. Além disso, são tradicionalmente implementados no runtime da linguagem, criando assim um sistema de escalonamento com dois níveis, onde a previsibilidade, essencial a um sistema de tempo real, não pode ser assegurada. Nesta tese, é descrita a forma como a abordagem de work-stealing pode ser resenhada para cumprir os requisitos de tempo real, mantendo, ao mesmo tempo, os seus princípios fundamentais que tão bons resultados têm demonstrado. Muito resumidamente, a única fila de gestão de processos convencional (deque) é substituída por uma fila de deques, ordenada de forma crescente por prioridade das tarefas. De seguida, aplicamos por cima o conhecido algoritmo de escalonamento dinâmico G-EDF, misturamos as regras de ambos, e assim nasce a nossa proposta: o algoritmo de escalonamento RTWS. Tirando partido da modularidade oferecida pelo escalonador do Linux, o RTWS é adicionado como uma nova classe de escalonamento, de forma a avaliar na prática se o algoritmo proposto é viável, ou seja, se garante a eficiência e escalonabilidade desejadas. Modificar o núcleo do Linux é uma tarefa complicada, devido à complexidade das suas funções internas e às fortes interdependências entre os vários subsistemas. Não obstante, um dos objetivos desta tese era ter a certeza que o RTWS é mais do que um conceito interessante. Assim, uma parte significativa deste documento é dedicada à discussão sobre a implementação do RTWS e à exposição de situações problemáticas, muitas delas não consideradas em teoria, como é o caso do desfasamento entre vários mecanismo de sincronização. Os resultados experimentais mostram que o RTWS, em comparação com outro trabalho prático de escalonamento dinâmico de tarefas com restrições temporais, reduz significativamente o overhead de escalonamento através de um controlo de migrações, e mudanças de contexto, eficiente e escalável (pelo menos até 8 CPUs), ao mesmo tempo que alcança um bom balanceamento dinâmico da carga do sistema, até mesmo de uma forma não custosa. Contudo, durante a avaliação realizada foi detetada uma falha na implementação do RTWS, pela forma como facilmente desiste de roubar trabalho, o que origina períodos de inatividade, no CPU em questão, quando a utilização geral do sistema é baixa. Embora o trabalho realizado se tenha focado em manter o custo de escalonamento baixo e em alcançar boa localidade dos dados, a escalonabilidade do sistema nunca foi negligenciada. Na verdade, o algoritmo de escalonamento proposto provou ser bastante robusto, não falhando qualquer meta temporal nas experiências realizadas. Portanto, podemos afirmar que alguma inversão de prioridades, causada pela sub-política de roubo BAS, não compromete os objetivos de escalonabilidade, e até ajuda a reduzir a contenção nas estruturas de dados. Mesmo assim, o RTWS também suporta uma sub-política de roubo determinística: PAS. A avaliação experimental, porém, não ajudou a ter uma noção clara do impacto de uma e de outra. No entanto, de uma maneira geral, podemos concluir que o RTWS é uma solução promissora para um escalonamento eficiente de tarefas paralelas com restrições temporais.

Off-line simulation inspires insight: a neurodynamics approach to efficient robot task learning

There is currently an increasing demand for robots able to acquire the sequential organization of tasks from social learning interactions with ordinary people. Interactive learning-by-demonstration and communication is a promising research topic in current robotics research. However, the efficient acquisition of generalized task representations that allow the robot to adapt to different users and contexts is a major challenge. In this paper, we present a dynamic neural field (DNF) model that is inspired by the hypothesis that the nervous system uses the off-line re-activation of initial memory traces to incrementally incorporate new information into structured knowledge. To achieve this, the model combines fast activation-based learning to robustly represent sequential information from single task demonstrations with slower, weight-based learning during internal simulations to establish longer-term associations between neural populations representing individual subtasks. The efficiency of the learning process is tested in an assembly paradigm in which the humanoid robot ARoS learns to construct a toy vehicle from its parts. User demonstrations with different serial orders together with the correction of initial prediction errors allow the robot to acquire generalized task knowledge about possible serial orders and the longer term dependencies between subgoals in very few social learning interactions. This success is shown in a joint action scenario in which ARoS uses the newly acquired assembly plan to construct the toy together with a human partner.

An Investigation of the Role of Attention in the Cross-Race Effect: An Ecological Approach

The current set of studies was conducted to examine the cross-race effect (CRE), a phenomenon commonly found in the face perception literature. The CRE is evident when participants display better own-race face recognition accuracy than other-race recognition accuracy (e.g. Ackerman et al., 2006). Typically the cross-race effect is attributed to perceptual expertise, (i.e., other-race faces are processed less holistically; Michel, Rossion, Han, Chung & Caldara, 2006), and the social cognitive model (i.e., other-race faces are processed at the categorical level by virtue of being an out-group member; Hugenberg, Young, Bernstein, & Sacco, 2010). These effects may be mediated by differential attention. I investigated whether other-race faces are disregarded and, consequently, not remembered as accurately as own-race (in-group) faces. In Experiment 1, I examined how the magnitude of the CRE differed when participants learned individual faces sequentially versus when they learned multiple faces simultaneously in arrays comprising faces and objects. I also examined how the CRE differed when participants recognized individual faces presented sequentially versus in arrays of eight faces. Participants’ recognition accuracy was better for own-race faces than other-race faces regardless of familiarization method. However, the difference between own- and other-race accuracy was larger when faces were familiarized sequentially in comparison to familiarization with arrays. Participants’ response patterns during testing differed depending on the combination of familiarization and testing method. Participants had more false alarms for other-race faces than own-race faces if they learned faces sequentially (regardless of testing strategy); if participants learned faces in arrays, they had more false alarms for other-race faces than own-races faces if ii i they were tested with sequentially presented faces. These results are consistent with the perceptual expertise model in that participants were better able to use the full two seconds in the sequential task for own-race faces, but not for other-race faces. The purpose of Experiment 2 was to examine participants’ attentional allocation in complex scenes. Participants were shown scenes comprising people in real places, but the head stimuli used in Experiment 1 were superimposed onto the bodies in each scene. Using a Tobii eyetracker, participants’ looking time for both own- and other-race faces was evaluated to determine whether participants looked longer at own-race faces and whether individual differences in looking time correlated with individual differences in recognition accuracy. The results of this experiment demonstrated that although own-race faces were preferentially attended to in comparison to other-race faces, individual differences in looking time biases towards own-race faces did not correlate with individual differences in own-race recognition advantages. These results are also consistent with perceptual expertise, as it seems that the role of attentional biases towards own-race faces is independent of the cognitive processing that occurs for own-race faces. All together, these results have implications for face perception tasks that are performed in the lab, how accurate people may be when remembering faces in the real world, and the accuracy and patterns of errors in eyewitness testimony.

Impacto da doença de Parkinson sobre as características cinéticas e cinemáticas da tarefa de levantar e andar, em caidores e não caidores

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Vergence control across saccades in dyslexic adults

Many aspects of vision have been investigated in developmental dyslexia. Some research suggests deficits in vergence control (e.g. Buzzelli, 1991, Optom. Vision Sci. 68, 842±846), although ability to control vergence across saccades has not yet been investigated. We have explored this question indirectly using Enright's (1996 Vision Res. 36, 307±312.) sequential stereopsis task. The task requires observers to set two adjacent targets (whose textures cannot be resolved simultaneously if either is fixated) to appear equi-distant. Enright has argued that sequential stereopsis stereoacuity thresholds offer an indication of vergence control across saccades. We report two experiments using a total of 17 dyslexic and 18 control adults. Performance was measured on a sequential stereopsis task and an ordinary `simultaneous' stereopsis task. No significant differences between groups were found. However, whereas practice of the sequential task lowered control group thresholds on the simultaneous task, for the dyslexic group it significantly raised thresholds, suggesting that visual fatigue is especially important in investigations of visual functions in dyslexia. Although the small samples used limit conclusions at this stage, the main sequential stereopsis results suggest that, if Enright is correct, dyslexic adults can show normal vergence control across saccades.

Effect of a sequential education and monitoring programme on quality-of-life components in heart failure

Aims Trials of disease management programmes (DMP) in heart failure (HF) have shown controversial results regarding quality of life. We hypothesized that a DMP applied over the long-term could produce different effects on each of the quality-of-life components. Methods and results We extended the prospective, randomized REMADHE Trial, which studied a DMP in HF patients. We analysed changes in Minnesota Living with Heart Failure Questionnaire components in 412 patients, 60.5% male, age 50.2 +/- 11.4 years, left ventricular ejection fraction 34.7 +/- 10.5%. During a mean follow-up of 3.6 +/- 2.2 years, 6.3% of patients underwent heart transplantation and 31.8% died. Global quality-of-life scores improved in the DMP intervention group, compared with controls, respectively: 57.5 +/- 3.1 vs. 52.6 +/- 4.3 at baseline, 32.7 +/- 3.9 vs. 40.2 +/- 6.3 at 6 months, 31.9 +/- 4.3 vs. 41.5 +/- 7.4 at 12 months, 26.8 +/- 3.1 vs. 47.0 +/- 5.3 at the final assessment; P<0.01. Similarly, the physical component (23.7 +/- 1.4 vs. 21.1 +/- 2.2 at baseline, 16.2 +/- 2.9 vs. 18.0 +/- 3.3 at 6 months, 17.3 +/- 2.9 vs. 23.1 +/- 5.7 at 12 months, 11.4 +/- 1.6 vs. 19.9 +/- 2.4 final; P<0.01), the emotional component (13.2 +/- 1.0 vs. 12.1 +/- 1.4 at baseline, 11.7 +/- 2.7 vs. 12.3 +/- 3.1 at 6 months, 12.4 +/- 2.9 vs. 16.8 +/- 5.9 at 12 months, 6.7 +/- 1.0 vs. 10.6 +/- 1.4 final; P<0.01) and the additional questions (20.8 +/- 1.2 vs. 19.3 +/- 1.8 at baseline, 14.3 +/- 2.7 vs. 17.3 +/- 3.1 at 6 months, 12.4 +/- 2.9 vs. 21.0 +/- 5.5 at 12 months, 6.7 +/- 1.4 vs. 17.3 +/- 2.2 final; P<0.01) were better (lower) in the intervention group. The emotional component improved earlier than the others. Post-randomization quality of life was not associated with events. Conclusion Components of the quality-of-life assessment responded differently to DMP. These results indicate the need for individualized DMP strategies in patients with HF. Trial registration information www.clincaltrials.gov NCT00505050-REMADHE.

On the Political Economy of Sequential Reforms

This paper proposes an explanation for why efficient reforms are not carried out when losers have the power to block their implementation, even though compensating them is feasible. We construct a signaling model with two-sided incomplete information in which a government faces the task of sequentially implementing two reforms by bargaining with interest groups. The organization of interest groups is endogenous. Compensations are distortionary and government types differ in the concern about distortions. We show that, when compensations are allowed to be informative about the government’s type, there is a bias against the payment of compensations and the implementation of reforms. This is because paying high compensations today provides incentives for some interest groups to organize and oppose subsequent reforms with the only purpose of receiving a transfer. By paying lower compensations, governments attempt to prevent such interest groups from organizing. However, this comes at the cost of reforms being blocked by interest groups with relatively high losses.

Contact Sensing: A Sequential Decision Approach to Sensing Manipulation Contact

This paper describes a new statistical, model-based approach to building a contact state observer. The observer uses measurements of the contact force and position, and prior information about the task encoded in a graph, to determine the current location of the robot in the task configuration space. Each node represents what the measurements will look like in a small region of configuration space by storing a predictive, statistical, measurement model. This approach assumes that the measurements are statistically block independent conditioned on knowledge of the model, which is a fairly good model of the actual process. Arcs in the graph represent possible transitions between models. Beam Viterbi search is used to match measurement history against possible paths through the model graph in order to estimate the most likely path for the robot. The resulting approach provides a new decision process that can be use as an observer for event driven manipulation programming. The decision procedure is significantly more robust than simple threshold decisions because the measurement history is used to make decisions. The approach can be used to enhance the capabilities of autonomous assembly machines and in quality control applications.

Problems in the coupling of eye and hand in the sequential movements of children with developmental coordination disorder

Background: Shifting gaze and attention ahead of the hand is a natural component in the performance of skilled manual actions. Very few studies have examined the precise co-ordination between the eye and hand in children with Developmental Coordination Disorder (DCD). Methods This study directly assessed the maturity of eye-hand co-ordination in children with DCD. A double-step pointing task was used to investigate the coupling of the eye and hand in 7-year-old children with and without DCD. Sequential targets were presented on a computer screen, and eye and hand movements were recorded simultaneously. Results There were no differences between typically developing (TD) and DCD groups when completing fast single-target tasks. There were very few differences in the completion of the first movement in the double-step tasks, but differences did occur during the second sequential movement. One factor appeared to be the propensity for the DCD children to delay their hand movement until some period after the eye had landed on the target. This resulted in a marked increase in eye-hand lead during the second movement, disrupting the close coupling and leading to a slower and less accurate hand movement among children with DCD. Conclusions In contrast to skilled adults, both groups of children preferred to foveate the target prior to initiating a hand movement if time allowed. The TD children, however, were more able to reduce this foveation period and shift towards a feedforward mode of control for hand movements. The children with DCD persevered with a look-then-move strategy, which led to an increase in error. For the group of DCD children in this study, there was no evidence of a problem in speed or accuracy of simple movements, but there was a difficulty in concatenating the sequential shifts of gaze and hand required for the completion of everyday tasks or typical assessment items.

How active gaze informs the hand in sequential pointing movements

Visual information is vital for fast and accurate hand movements. It has been demonstrated that allowing free eye movements results in greater accuracy than when the eyes maintain centrally fixed. Three explanations as to why free gaze improves accuracy are: shifting gaze to a target allows visual feedback in guiding the hand to the target (feedback loop), shifting gaze generates ocular-proprioception which can be used to update a movement (feedback-feedforward), or efference copy could be used to direct hand movements (feedforward). In this experiment we used a double-step task and manipulated the utility of ocular-proprioceptive feedback from eye to head position by removing the second target during the saccade. We confirm the advantage of free gaze for sequential movements with a double-step pointing task and document eye-hand lead times of approximately 200 ms for both initial movements and secondary movements. The observation that participants move gaze well ahead of the current hand target dismisses foveal feedback as a major contribution. We argue for a feedforward model based on eye movement efference as the major factor in enabling accurate hand movements. The results with the double-step target task also suggest the need for some buffering of efference and ocular-proprioceptive signals to cope with the situation where the eye has moved to a location ahead of the current target for the hand movement. We estimate that this buffer period may range between 120 and 200 ms without significant impact on hand movement accuracy.

Production and processing asymmetries in the acquisition of tense morphology by sequential bilingual children

This study investigates the production and on-line processing of English tense morphemes by sequential bilingual (L2) Turkish-speaking children with more than three years of exposure to English. Thirty nine 6-9-year-old L2 children and 28 typically developing age-matched monolingual (L1) children were administered the production component for third person –s and past tense of the Test for Early Grammatical Impairment (Rice & Wexler, 1996) and participated in an on-line word-monitoring task involving grammatical and ungrammatical sentences with presence/omission of tense (third person –s, past tense -ed) and non-tense (progressive –ing, possessive ‘s) morphemes. The L2 children’s performance on the on-line task was compared to that of children with Specific Language Impairment (SLI) in Montgomery & Leonard (1998, 2006) to ascertain similarities and differences between the two populations. Results showed that the L2 children were sensitive to the ungrammaticality induced by the omission of tense morphemes, despite variable production. This reinforces the claim about intact underlying syntactic representations in child L2 acquisition despite non target-like production (Haznedar & Schwartz, 1997).

Parsing the passive: comparing children with Specific Language Impairment to sequential bilingual children

25 monolingual (L1) children with Specific Language Impairment (SLI), 32 sequential bilingual (L2) children, and 29 L1 controls completed the Test of Active & Passive Sentences-Revised (van der Lely, 1996) and the self-paced listening task with picture verification for actives and passives (Marinis, 2007). These revealed important between-group differences in both tasks. The children with SLI showed difficulties in both actives and passives when they had to reanalyse thematic roles on-line. Their error pattern provided evidence for working memory limitations. The L2 children showed difficulties only in passives both on-line and off-line. We suggest that these relate to the complex syntactic algorithm in passives and reflect an earlier developmental stage due to reduced exposure to the L2. The results are discussed in relation to theories of SLI and can be best accommodated within accounts proposing that difficulties in the comprehension of passives stem from processing limitations.

Production and on-line comprehension of definite articles and clitic pronouns by Greek sequential bilingual children and monolingual children with specific language impairment

The present study compared production and on-line comprehension of definite articles and third person direct object clitic pronouns in Greek-speaking typically developing, sequential bilingual (L2-TD) children and monolingual children with specific language impairment (L1-SLI). Twenty Turkish Greek L2-TD children, 16 Greek L1-SLI children, and 31 L1-TD Greek children participated in a production task examining definite articles and clitic pronouns and, in an on-line comprehension task, involving grammatical sentences with definite articles and clitics and sentences with grammatical violations induced by omitted articles and clitics. The results showed that the L2-TD children were sensitive to the grammatical violations despite low production. In contrast, the children with SLI were not sensitive to clitic omission in the on-line task, despite high production. These results support a dissociation between production and on-line comprehension in L2 children and for impaired grammatical representations and lack of automaticity in children with SLI. They also suggest that on-line comprehension tasks may complement production tasks by differentiating between the language profiles of L2-TD children and children with SLI.

Production and on-line comprehension of definiteness in English and Dutch by monolingual and sequential bilingual children

The present article examines production and on-line processing of definite articles in Turkish-speaking sequential bilingual children acquiring English and Dutch as second languages (L2) in the UK and in the Netherlands, respectively. Thirty-nine 6–8-year-old L2 children and 48 monolingual (L1) age-matched children participated in two separate studies examining the production of definite articles in English and Dutch in conditions manipulating semantic context, that is, the anaphoric and the bridging contexts. Sensitivity to article omission was examined in the same groups of children using an on-line processing task involving article use in the same semantic contexts as in the production task. The results indicate that both L2 children and L1 controls are less accurate when definiteness is established by keeping track of the discourse referents (anaphoric) than when it is established via world knowledge (bridging). Moreover, despite variable production, all groups of children were sensitive to the omission of definite articles in the on-line comprehension task. This suggests that the errors of omission are not due to the lack of abstract syntactic representations, but could result from processes implicated in the spell-out of definite articles. The findings are in line with the idea that variable production in child L2 learners does not necessarily indicate lack of abstract representations (Haznedar and Schwartz, 1997).