Department of Computer Science

Inspired by recent human studies, this paper investigates the benefits of employing varying navigation strategies in robot teams. We explore how mixed navigation strategies impact task completion time, environment exploration, and overall system effectiveness in multi-robot systems. Experiments were conducted in a simulated rectangular environment using Clearpath PR2 robots and evaluated different navigation strategies observed in humans: 1) Route (RT) knowledge where agents follow a predefined path, 2) Survey (SW) knowledge where agents take the shortest path while avoiding obstacles, 3) Mixed strategies with varying proportions, such as 40% RT and 60% SW (0.4RT 0.6SW) and 60% RT and 40% SW (0.6RT 0.4SW), and 4) An additional strategy where agents switch from RT to SW 10% of the time (0.9RT 0.1SW). While SW strategy is the most time-efficient, RT strategy covers more of the environment. Mixed strategies offer a balanced trade-off. These findings highlight the advantages of variability in navigation strategies, suggesting benefits in both biological and robotic populations. Additionally, we have observed that human participants in a similar study would start on a route, and then 10% of the time switch to survey. Therefore, we investigate a 90% Route 10% Survey (0.9RT 0.1SW) strategy for individual team members. While a pure Survey strategy is the most efficient regarding time taken and a pure Route strategy covers more of the environment, a mixture of strategies appears to be a beneficial tradeoff between time taken to complete a mission and area coverage. These results highlight the advantages of population variability, suggesting potential benefits in both biological and robotic populations.

Generative Artificial Intelligence is set to revolutionize healthcare delivery by transforming traditional patient care into a more personalized, efficient, and proactive process. Chatbots, serving as interactive conversational models, will probably drive this patient-centered transformation in healthcare. Through the provision of various services, including diagnosis, personalized lifestyle recommendations, dynamic scheduling of follow-ups, and mental health support, the objective is to substantially augment patient health outcomes, all the while mitigating the workload burden on healthcare providers. The life-critical nature of healthcare applications necessitates establishing a unified and comprehensive set of evaluation metrics for conversational models. Existing evaluation metrics proposed for various generic large language models (LLMs) demonstrate a lack of comprehension regarding medical and health concepts and their significance in promoting patients’ well-being. Moreover, these metrics neglect pivotal user-centered aspects, including trust-building, ethics, personalization, empathy, user comprehension, and emotional support. The purpose of this paper is to explore state-of-the-art LLM-based evaluation metrics that are specifically applicable to the assessment of interactive conversational models in healthcare. Subsequently, we present a comprehensive set of evaluation metrics designed to thoroughly assess the performance of healthcare chatbots from an end-user perspective. These metrics encompass an evaluation of language processing abilities, impact on real-world clinical tasks, and effectiveness in user-interactive conversations. Finally, we engage in a discussion concerning the challenges associated with defining and implementing these metrics, with particular emphasis on confounding factors such as the target audience, evaluation methods, and prompt techniques involved in the evaluation process.

We study algorithms for drawing planar graphs and 1-planar graphs using cubic Bézier curves with bounded curvature. We show that any n-vertex 1-planar graph has a 1-planar RAC drawing using a single cubic Bézier curve per edge, and this drawing can be computed in O(n) time given a combinatorial 1-planar drawing. We also show that any n-vertex planar graph G can be drawn in O(n) time with a single cubic Bézier curve per edge, in an O(n) × O(n) bounding box, such that the edges have Θ(1/degree(v)) angular resolution, for each v ∈ G, and O(√ n) curvature.

Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing.

Spatial transcriptomics has transformed genomic research by measuring spatially resolved gene expressions, allowing us to investigate how cells adapt to their microenvironment via modulating their expressed genes. This essential process usually starts from cell-cell communication (CCC) via ligand-receptor (LR) interaction, leading to regulatory changes within the receiver cell. However, few methods were developed to connect them to provide biological insights into intercellular regulation. To fill this gap, we propose iMiracle, an iterative multi-view graph neural network that models each cells intercellular regulation with three key features. Firstly, iMiracle integrates inter- and intra-cellular networks to jointly estimate cell-type- and micro-environment-driven gene expressions. Optionally, it allows prior knowledge of intra-cellular networks as pre-structured masks to maintain biological relevance. Secondly, iMiracle employs iterative learning to overcome the sparsity of spatial transcriptomic data and gradually fill in the missing edges in the CCC network. Thirdly, iMiracle infers a cell-specific ligand-gene regulatory score based on the contributions of different LR pairs to interpret inter-cellular regulation. We applied iMiracle to nine simulated and eight real datasets from three sequencing platforms and demonstrated that iMiracle consistently outperformed ten methods in gene expression imputation and four methods in regulatory score inference. Lastly, we developed iMiracle as an open-source software and anticipate that it can be a powerful tool in decoding the complexities of inter-cellular transcriptional regulation.

Single-cell sequencing technologies have revolutionized genomics by enabling the simultaneous profiling of various molecular modalities within individual cells. Their integration, especially cross-modality translation, offers deep insights into cellular regulatory mechanisms. Many methods have been developed for cross-modality translation, but their reliance on scarce high-quality co-assay data limits their applicability. Addressing this, we introduce scACT, a deep generative model designed to extract cross-modality biological insights from unpaired single-cell data. scACT tackles three major challenges: aligning unpaired multi-modal data via adversarial training, facilitating cross-modality translation without prior knowledge via cycle-consistent training, and enabling interpretable regulatory interconnections explorations via in-silico perturbations. To test its performance, we applied scACT on diverse single-cell datasets and found it outperformed existing methods in all three tasks. Finally, we have developed scACT as an individual open-source software package to advance single-cell omics data processing and analysis within the research community.

Alon, Seymour, and Thomas [J. Amer. Math. Soc., 3 (1990), pp. 801-808] proved that every n-vertex graph excluding Kt as a minor has treewidth less than t3/2 \surdn. Illingworth, Scott, and Wood [Product Structure of Graphs with an Excluded Minor, preprint, arXiv:2104.06627, 2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth t - 2, where each vertex is blown up by a complete graph of order \scrO(\surdtn). Solving an open problem of Illingworth, Scott, and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order \scrOt(\surdn). As an extension of the Lipton-Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalize this result for K3,t-minor-free graphs, with blowups of order \scrO(t\surdn). This setting includes graphs embeddable on any fixed surface.

Ventral tegmental area (VTA) dopamine neurons regulate reward-related associative learning and reward-driven motivated behaviors, but how these processes are coordinated by distinct VTA neuronal subpopulations remains unresolved. Here, we compare the contribution of two primarily dopaminergic and largely non-overlapping VTA subpopulations, all VTA dopamine neurons and VTA GABAergic neurons of the mouse midbrain, to these processes. We find that the dopamine subpopulation that projects to the nucleus accumbens (NAc) core preferentially encodes reward-predictive cues and prediction errors. In contrast, the subpopulation that projects to the NAc shell preferentially encodes goal-directed actions and relative reward anticipation. VTA GABA neuron activity strongly contrasts VTA dopamine population activity and preferentially encodes reward outcome and retrieval. Electrophysiology, targeted optogenetics, and whole-brain input mapping reveal multiple convergent sources that contribute to the heterogeneity among VTA dopamine subpopulations that likely underlies their distinct encoding of reward-related associations and motivation that defines their functions in these contexts.

Prolyl oligopeptidases from psychrophilic, mesophilic, and thermophilic organisms found in a range of natural environments are studied using a combination of protein structure prediction, atomistic molecular dynamics, and trajectory analysis to determine how the S9 protease family adapts to extreme thermal conditions. We compare our results with hypotheses from the literature regarding structural adaptations that allow proteins to maintain structure and function at extreme temperatures, and we find that, in the case of prolyl oligopeptidases, only a subset of proposed adaptations are employed for maintaining stability. The catalytic and propeller domains are highly structured, limiting the range of mutations that can be made to enhance hydrophobicity or form disulfide bonds without disrupting the formation of necessary secondary structure. Rather, we observe a pattern in which overall prevalence of bound interactions (salt bridges and hydrogen bonds) is conserved by using increasing numbers of increasingly short-lived interactions as temperature increases. This suggests a role for an entropic rather than energetic strategy for thermal adaptation in this protein family.