Real‐time density‐based crowd simulation

Virtual characters in games and simulations often need to plan visually convincing paths through a crowded environment. This paper describes how crowd density information can be used to guide a large number of characters through a crowded environment. Crowd density information helps characters avoid congested routes that could lead to traffic jams. It also encourages characters to use a wide variety of routes to reach their destination. Our technique measures the desirability of a route by combining distance information with crowd density information. We start by building a navigation mesh for the walkable regions in a polygonal two‐dimensional (2‐D) or multilayered three‐dimensional (3‐D) environment. The skeleton of this navigation mesh is the medial axis. Each walkable region in the navigation mesh maintains an up‐to‐date density value. This density value is equal to the area occupied by all the characters inside a given region divided by the total area of this region. These density values are mapped onto the medial axis to form a weighted graph. An A^* search on this graph yields a backbone path for each character, and forces are used to guide the characters through the weighted environment. The characters periodically replan their routes as the density values are updated. Our experiments show that we can compute congestion‐avoiding paths for tens of thousands of characters in real‐time. Copyright © 2012 John Wiley & Sons, Ltd.     

并行群体仿真研究进展

通过对比分析基于多核CPU、GPU和分布式系统等三种并行群体仿真体系结构,提出了混合结构的并行群体仿真框架;对并行环境下的按空间区域分割和按agent分割等多种任务分割关键算法进行了归纳总结;对并行群体仿真的性能评估方法进行了分析。最终给出了群体仿真中并行加速算法的研究方向。     

基于GPU的大规模人群疏散模拟*

基于中央处理器(CPU)串行的人群疏散传统方法对于人群规模较少的场景,可以得到良好的疏散模拟效果,但在人群密度较高的场景中,难以达到实时模拟的要求。为了克服上述问题,实现了一种基于图形处理器(GPU)的人群疏散模拟的方法。该方法通过对个体寻径算法的优化,不仅能使个体快速准确地智能寻径,而且将个体寻径独立性与图形处理器高性能计算特性进行结合,充分利用了图形处理器强大的并行计算能力,从而大幅度提高了人群疏散模拟的人群规模,使人群疏散模拟的实时性得到增强。     

折半聚类算法在基于社会力的人群疏散仿真中的应用

运用社会力模型（SFM）模拟人群疏散之前,需要先对人群进行聚类分组;然而,k中心聚类（k-medoids）和统计信息网格聚类（STING）这两大传统聚类算法,在聚类效率和准确率上都不能满足要求。针对这个问题,提出了折半聚类算法（BCA）。该算法结合了围绕中心点聚类和基于网格聚类两类方式,并利用二分法查找思想划分网格,不需要反复聚类。先将数据用二分法划分成网格,再根据网格内数据密度选出核心网格,接着以核心网格为中心将邻居网格聚类,最后按就近原则归并剩余网格。实验结果表明,在聚类时间上,BCA平均仅是STING算法的48.3%,不到k-medoids算法的14%;而在聚类准确率上,k-medoids算法平均仅是BCA的50%,STING算法平均也只是BCA的88%。因此,BCA无论在效率还是准确率上都明显优于STING和k-medoids算法。     

基于密度聚类算法的校园人群聚集和移动规律分析

针对某高校无线网日志数据进行挖掘分析,获取校园人群聚集点分布和人群移动规律。首先利用分布式统计算法统计校园内各建筑物的无线网络连接人次;然后建立校园建筑物的中心点经纬坐标的R树索引,并对R树叶子节点分组,以此将校园分成几个部分;再利用密度聚类算法对校园每一个部分中的建筑物中心点经纬坐标进行聚类得到校园区域划分;最后结合聚类结果和统计结果获取人群聚集区域和区域之间人群移动规律。研究结果可为学校校车路径规划、共享单车部署和校园功能区规划等工作提供参考。     

Density‐enhanced perceptual mosaic on GPU

Image mosaic effects are wildly applied in print media, domestic decoration, and many image beautification applications. However, the current image mosaic methods are mostly based on fixed‐size image tiles, simple color adjustment, and irregular image segmentation, which are inaccurate and very time‐consuming. In this paper, we present a graphics processing unit‐accelerated perceptual mosaic using density tiles replacement and brightness lighting optimization, keeping original image structure details and providing more expressive visual effects. Automatic density replacement map segmentation and color‐based region tiles replacement are performed to facilitate the mosaic. Delicate brightness optimization and perceptual color correction are further applied to enhance expressive lighting effects. We also consider the salience perception of images and similarity correlation among neighboring tiles for our perceptual mosaic. The experimental results have shown the efficiency and high‐quality performance of our density‐enhanced perceptual mosaic on graphics processing unit. Copyright © 2016 John Wiley & Sons, Ltd.     

Improving responsiveness of time‐sensitive applications by exploiting dynamic task dependencies

In this paper, a mechanism is presented for reducing priority inversion in multiprogrammed computing systems. Contrary to well‐known approaches from the literature, this paper tackles cases where the dependency relationships among tasks cannot be known in advance to the operating system. The presented mechanism allows tasks to explicitly declare aforementioned relationships, enabling the operating system scheduler to take advantage of such information and trigger priority inheritance, resulting in reduced priority inversion. We present the prototype implementation of the concept within the Linux kernel in the form of modifications to the standard Portable Operating System Interface (POSIX) condition variable code, along with an extensive evaluation, including a quantitative assessment of the benefits for applications making use of the technique and comprehensive overhead measurements. In addition, we present an associated technique for the theoretical schedulability analysis of a system using the new mechanism, which is useful to determine whether all tasks can meet their deadlines or not, in the specific scenario of tasks interacting only through remote procedure calls and under partitioned scheduling.     

Implementation of a constant‐time dynamic storage allocator

This paper describes the design criteria and implementation details of a dynamic storage allocator for real‐time systems. The main requirements that have to be considered when designing a new allocator are concerned with temporal and spatial constraints. The proposed algorithm, called TLSF (two‐level segregated fit), has an asymptotic constant cost, O(1), maintaining a fast response time (less than 200 processor instructions on a x86 processor) and a low level of memory usage (low fragmentation). TLSF uses two levels of segregated lists to arrange free memory blocks and an incomplete search policy. This policy is implemented with word‐size bitmaps and logical processor instructions. Therefore, TLSF can be categorized as a good‐fit allocator. The incomplete search policy is shown also to be a good policy in terms of fragmentation. The fragmentation caused by TLSF is slightly smaller (better) than that caused by best fit (which is one of the best allocators regarding memory fragmentation). In order to evaluate the proposed allocator, three analyses are presented in this paper. The first one is based on worst‐case scenarios. The second one provides a detailed consideration of the execution cost of the internal operations of the allocator and its fragmentation. The third analysis is a comparison with other well‐known allocators from the temporal (number of cycles and processor instructions) and spatial (fragmentation) points of view. In order to compare them, a task model has been presented. Copyright © 2007 John Wiley & Sons, Ltd.     

Composing and scheduling service‐oriented applications in time‐triggered distributed real‐time Java environments

During the last decade, the number of distributed application domains with temporal requirements has significantly augmented, arising the necessity of exploring new concepts and paradigms that allow, on the one hand, the development of dynamic and flexible distributed applications and, on the other hand, the reusability of code. Service‐oriented paradigms have been successfully applied to distributed environments, increasing their flexibility and allowing the reusability of their components. Besides, distributed real‐time Java technologies have shown to be a good candidate to deploy real‐time distributed applications. This paper presents a model for service‐oriented applications on a time‐triggered distributed real‐time Java environment, focusing on the definition of the temporal model of an application and its schedulability, applying and evaluating this model in real‐time service‐oriented composition algorithms. Copyright © 2012 John Wiley & Sons, Ltd.     

人群应急疏散可视仿真研究进展和问题

人群应急疏散可视仿真是用智能体来模拟具有自主感知、情绪和行为能力的人群个体,并采用3维可视的方式来直观呈现人群应急疏散情景,可以为制定人群应急预案提供形象直观的分析方法。本文从人群仿真数据的来源、人群导航模型的构建、人群行为模型、人群情绪感染、人群渲染5个方面概述目前研究的进展,然后从仿真模型的可验证性、人群疏散导航模型的构建、人与环境的物理模型、动物逃生实验与仿真、疏散中的社会行为表现以及人群情绪的可视计算6个角度讨论需要进一步研究的问题。针对需要深入研究的问题,指出借助于紧急事件的视频监控分析和虚拟人群情景的用户调查,有助于完善人群仿真模型。结合物理模型,可以更准确地描述人群应急疏散场景。开展动物逃生实验分析,有助于完善人群运动导航算法。建立人群社会行为模型,可以更详细描述疏散中人群行为的多样性。构建基于多通道感知的人群情绪感染计算方法,可以详尽描述情绪感染的过程。人群应急疏散行为的可视仿真研究在城市的安全管理方面具有重要的应用前景,但其研究仍存在很多亟待解决的问题,综合地运用多学科知识,完善实验手段是进一步推动研究的关键所在。     

An improved branch‐and‐bound clustering approach for data partitioning

In this paper, we are concerned with clustering algorithms for vertical partitioning. In particular, we examine the use of a branch‐and‐bound scheme. An existing algorithm using such a scheme may produce infeasible solutions to some problems. We adopt the same branch‐and‐bound scheme and develop a new branching strategy to avoid infeasibility. Illustrative examples are used to demonstrate the effectiveness of our new approach. In addition, we also show how to formulate the horizontal partitioning problem such that the same algorithm can be applied.     

Implementation of a TMO‐structured real‐time airplane‐landing simulator on a distributed computing environment

In real‐time simulation, the simulated system should display the same (or very close) timing behavior as the target system. The simulation accuracy is increased as the simulation time unit is decreased. Although there are several models for such systems, the TMO model is particularly appropriate due to its natural support for real‐time distributed object‐oriented programming. This paper discusses the results of the implementation of a real‐time airplane‐landing simulator on a distributed computing environment using the TMO model. Copyright © 2004 John Wiley & Sons, Ltd.     

Alternating optimization to solve penalized regression‐based clustering model

Two previously proposed heuristic algorithms for solving penalized regression‐based clustering model (PRClust) are (a) an algorithm that combines the difference‐of‐convex programming with a coordinate‐wise descent (DC‐CD) algorithm and (b) an algorithm that combines DC with the alternating direction method of multipliers (DC‐ADMM). In this paper, a faster method is proposed for solving PRClust. DC‐CD uses p × n × (n ? 1)/2 slack variables to solve PRClust, where n is the number of data and p is the number of their features. In each iteration of DC‐CD, these slack variable and cluster centres are updated using a second‐order cone programming (SOCP). DC‐ADMM uses p × n × (n ? 1) slack variables. In each iteration of DC‐ADMM, these slack variables and cluster centres are updated using ADMM. In this paper, PRClust is reformulated into an equivalent model to be solved using alternating optimization. Our proposed algorithm needs only n × (n ? 1)/2 slack variables, which is much less than that of DC‐CD and DC‐ADMM and updates them analytically using a simple equation in each iteration of the algorithm. Our proposed algorithm updates only cluster centres using an SOCP. Therefore, our proposed SOCP is much smaller than that of DC‐CD, which is used to update both cluster centres and slack variables. Experimental results on real datasets confirm that our proposed method is faster and much faster than DC‐ADMM and DC‐CD, respectively.     

A simulated annealing‐based maximum‐margin clustering algorithm

Maximum‐margin clustering is an extension of the support vector machine (SVM) to clustering. It partitions a set of unlabeled data into multiple groups by finding hyperplanes with the largest margins. Although existing algorithms have shown promising results, there is no guarantee of convergence of these algorithms to global solutions due to the nonconvexity of the optimization problem. In this paper, we propose a simulated annealing‐based algorithm that is able to mitigate the issue of local minima in the maximum‐margin clustering problem. The novelty of our algorithm is twofold, ie, (i) it comprises a comprehensive cluster modification scheme based on simulated annealing, and (ii) it introduces a new approach based on the combination of k‐means++ and SVM at each step of the annealing process. More precisely, k‐means++ is initially applied to extract subsets of the data points. Then, an unsupervised SVM is applied to improve the clustering results. Experimental results on various benchmark data sets (of up to over a million points) give evidence that the proposed algorithm is more effective at solving the clustering problem than a number of popular clustering algorithms.     

Enhancing OSGi with real‐time Java support

OSGi was designed with embedded systems in mind, its current support is insufficient for coping with one main characteristic of many embedded systems: real‐time performance. This article analyzes different key issues in providing OSGi with real‐time Java performance covering motivational issues, and different integration ways and challenges stemming from the integration. It also contributes a general framework for introducing real‐time performance in OSGi, which is called the real‐time for OSGi framework. The framework uses real‐time Java virtual machines and the real‐time specification for Java. The adoption of this framework allows cyber‐physical systems to experience real‐time Java performance in their applications. The framework introduces several integration levels for OSGi and real‐time specification for Java, and specific real‐time OSGi services. An empirical implementation was carried out using standard software, which was extended with the new defined services. Copyright © 2012 John Wiley & Sons, Ltd.     

无线传感器网络本地集中式动态成簇算法研究

为了缩短簇型无线传感器网络的成簇时间、延长网络寿命,提出了一种本地集中式动态成簇算法。对LEACH算法的成簇过程进行了认知与分解,指出了簇密度不均匀是成簇时间延长的主要原因。在此基础上建立了总体设计模型,对簇密度进行了自适应调整,采用簇内节点数阈值控制的簇分裂和簇合并,从而避免了簇密度过大或过小的情况。提出了簇头意外失效时补选簇头和网络层功率控制优化策略。改进的J-Sim仿真实验结果表明,该算法有效地延长了网络寿命。     

Graphics processing unit‐accelerated bounding for branch‐and‐bound applied to a permutation problem using data access optimization

Branch‐and‐bound (B&B) algorithms are attractive methods for solving to optimality combinatorial optimization problems using an implicit enumeration of a dynamically built tree‐based search space. Nevertheless, they are time‐consuming when dealing with large problem instances. Therefore, pruning tree nodes (subproblems) is traditionally used as a powerful mechanism to reduce the size of the explored search space. Pruning requires to perform the bounding operation, which consists of applying a lower bound function to the subproblems generated during the exploration process. Preliminary experiments performed on the Flow‐Shop scheduling problem (FSP) have shown that the bounding operation consumes over 98% of the execution time of the B&B algorithm. In this paper, we investigate the use of graphics processing unit (GPU) computing as a major complementary way to speed up the search. We revisit the design and implementation of the parallel bounding model on GPU accelerators. The proposed approach enables data access optimization. Extensive experiments have been carried out on well‐known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU‐based single core execution using an Intel Core i7‐970 processor without GPU, speedups higher than 100 times faster are achieved for large problem instances. At an equivalent peak performance, GPU‐accelerated B&B is twice faster than its multi‐core counterpart. Copyright © 2013 John Wiley & Sons, Ltd.     

Simulation of resource synchronization in a dynamic real‐time distributed computing environment

Today, more and more distributed computer applications are being modeled and constructed using real‐time principles and concepts. In 1989, the Object Management Group (OMG) formed a Real‐Time Special Interest Group (RT SIG) with the goal of extending the Common Object Request Broker Architecture (CORBA) standard to include real‐time specifications. This group's most recent efforts have focused on the requirements of dynamic distributed real‐time systems. One open problem in this area is resource access synchronization for tasks employing dynamic priority scheduling. This paper presents two resource synchronization protocols that the authors have developed which meet the requirements of dynamic distributed real‐time systems as specified by Dynamic Scheduling Real‐Time CORBA (DSRT CORBA). The proposed protocols can be applied to both Earliest Deadline First (EDF) and Least Laxity First (LLF) dynamic scheduling algorithms, allow distributed nested critical sections, and avoid unnecessary runtime overhead. In order to evaluate the performance of the proposed protocols, we analyzed each protocol's schedulability. Since the schedulability of the system is affected by numerous system configuration parameters, we have designed simulation experiments to isolate and illustrate the impact of each individual system parameter. Simulation experiments show the proposed protocols have better performance than one would realize by applying a schema that utilizes dynamic priority ceiling update. Copyright © 2004 John Wiley & Sons, Ltd.     

Design and analysis of target‐sensitive real‐time systems

A significant number of real‐time control applications include computational activities where the results have to be delivered at precise instants, rather than within a deadline. The performance of such systems significantly degrades if outputs are generated before or after the desired target time. This work presents a general methodology that can be used to design and analyze target‐sensitive applications in which the timing parameters of the computational activities are tightly coupled with the physical characteristics of the system to be controlled. For the sake of clarity, the proposed methodology is illustrated through a sample case study used to show how to derive and verify real‐time constraints from the mission requirements. Software implementation issues necessary to map the computational activities into tasks running on a real‐time kernel are also discussed to identify the kernel mechanisms necessary to enforce timing constraints and analyze the feasibility of the application. A set of experiments are finally presented with the purpose of validating the proposed methodology. Copyright © 2015 John Wiley & Sons, Ltd.     

Real‐time generation of smoothed‐particle hydrodynamics‐based special effects in character animation

In the previous works, the real‐time fluid‐character animation could hardly be achieved because of the intensive processing demand on the character's movement and fluid simulation. This paper presents an effective approach to the real‐time generation of the fluid flow driven by the motion of a character in full 3D space, based on smoothed‐particle hydrodynamics method. The novel method of conducting and constraining the fluid particles by the geometric properties of the character motion trajectory is introduced. Furthermore, the optimized algorithms of particle searching and rendering are proposed, by taking advantage of the graphics processing unit parallelization. Consequently, both simulation and rendering of the 3D liquid effects with realistic character interactions can be implemented by our framework and performed in real‐time on a conventional PC. Copyright © 2013 John Wiley & Sons, Ltd.