Articoli di riviste sul tema "Forward reachable set"

Most of the existing influence maximization algorithms are not suitable for large-scale social networks due to their high time complexity or limited influence propagation range. Therefore, a D-RIS (dynamic-reverse reachable set) influence maximization algorithm is proposed based on the independent cascade model and combined with the reverse reachable set sampling. Under the premise that the influence propagation function satisfies monotonicity and submodularity, the D-RIS algorithm uses an automatic debugging method to determine the critical value of the number of reverse reachable sets, which not only obtains a better influence propagation range but also greatly reduces the time complexity. The experimental results on the two real datasets of Slashdot and Epinions show that D-RIS algorithm is close to the CELF (cost-effective lazy-forward) algorithm and higher than RIS algorithm, HighDegree algorithm, LIR algorithm, and pBmH (population-based metaheuristics) algorithm in influence propagation range. At the same time, it is significantly better than the CELF algorithm and RIS algorithm in running time, which indicates that D-RIS algorithm is more suitable for large-scale social network.

This paper discusses the inverse and forward kinematics problem for a 2-dof parallel robot with actuator redundancy. The reachable workspace of the robot is generated for a set of parameters and a solution for the actuators is proposed in the final.

AbstractFormal analysis of the emergent structural properties of dynamic networks is largely uncharted territory. We focus here on the properties of forward reachable sets (FRS) as a function of the underlying degree distribution and edge duration. FRS are defined as the set of nodes that can be reached from an initial seed via a path of temporally ordered edges; a natural extension of connected component measures to dynamic networks. Working in a stochastic framework, we derive closed-form expressions for the mean and variance of the exponential growth rate of the FRS for temporal networks with both edge and node dynamics. For networks with node dynamics, we calculate thresholds for the growth of the FRS. The effects of finite population size are explored via simulation and approximation. We examine how these properties vary by edge duration and different cross-sectional degree distributions that characterize a range of scientifically interesting normative outcomes (Poisson and Bernoulli). The size of the forward reachable set gives an upper bound for the epidemic size in disease transmission network models, relating this work to epidemic modeling (Ferguson, 2000; Eames, 2004).

We construct a theory of forward guidance in economic policy making in order to provide a framework for explaining the role and strategic advantages of including forward guidance as an explicit part of policy design. We do this by setting up a general policy problem in which forward guidance plays a role, and then examine the consequences for performance when that guidance is withdrawn. We show that forward guidance provides enhanced controllability and stabilizability—especially where such properties may not otherwise be available. As a by-product, we find that forward guidance limits the scope and incentives for time-inconsistent behavior in an economy whose policy goals are ultimately reachable. It also adds to the credibility of a set of policies.

In software design of complex systems, more time and effort are spent on verification than on constructions. Model checking for software verification techniques offer a large potential to obtain and early integration of verification in the design process. This paper describes how to easily specify and the software properties and to understand the software generating automatically invariant. In this paper deal with issue that state invariant is a property that holds in every reachable state. Not only can be used in understanding and analysis of complex software systems. In addition, it can be used for system verifications such as checking safety, consistency, and completeness. For these reasons, there are many vital researches for deriving state invariant from finite state machine models. In this research was to be considered to extract state invariant. Thus it is likely to be too complex for the user to understand. This paper let the user focus on some interested parts (called scopes) rather than a whole state space in a model. Computation Tree Logic (CTL) is used to specify scopes in which he/she is interested. Given a scope in CTL, forward reachability analysis is used to find out a set of states inside it. Obviously, a set of states calculated in this way is a subset of every reachable state. Keywords: Software verification, Invariant, Scopes, Model Checking

Software reliability is one of the most important quality indices in software quality evaluation. Reliability analysis based on software architecture has become a researching hotspot. This paper makes a review on existed architecture-based reliability evaluation models, and puts forward the shortage of these models. As petri net has a good ability of description for concurrency and asynchronism, this paper focuses on the research of petri net model. Transitions are divided into time transitions and instantaneous transitions. Time-related reliability, including time-delay reliability and temporal reliability, are added. Then the reachable state transition matrix is set up and system reliability evaluation proceeds. The method above is used into a avionics embedded software. At last we accomplish the architecture modeling, reliability evaluation, proving the effectiveness and feasibility of this method.

<p><strong>Abstract.</strong> With the popularity of mobile positioning devices, mobile trajectory data is rapidly increasing. The trajectory stay feature extraction is to find the staying part of the moving object from the moving trajectory, which is the basis of the semantic matching of the staying segment. The trajectory stay segment extraction can be used to analyze tourist visit recommendation and mode, special landmark extraction such as gas station, destination prediction, rental car passenger advice, and even traffic guidance. Most existing researches extract the single-scale stay feature of the trajectory through the spatiotemporal characteristics of the trajectory or the geographical environment. However, the stay feature of the trajectory is multi-scale. For example, at a city scale, the stay of a tourist trajectory is composed of several scenic spots; however, at the scenic scale, a scenic stop may contain a number of subtle attraction. Therefore, this paper proposes to extract trajectory multi-scale stay feature based on OPTICS method. Since the trajectory data is different from the conventional discrete point set, but an ordered point string, the OPTICS method needs to be modified to accommodate the clustering of the trajectory point string. Method improvements include the following four aspects:</p><p>(1)The correction of the two-point distance definition of the trajectory. Since the trajectory points are ordered, thedistance between the two points of the trajectory is not the linear distance between the two points, but the sum of thelengths of the trajectory polylines between the two points.</p><p>(2)The count calculation of points in the ε neighborhood of the center points needs to be improved. When the timeinterval of the trajectory is equal, the calculation method is consistent with OPTICS; and when the time interval of thetrajectory sampling is not equal, the number of points represented by one trajectory points should be related to its timeinterval. When the time interval is large, the point should represent more points. Therefore, a time coefficient is defined,which is defined as the ratio of the track point time interval to the basic time interval. The total number of the points isthe sum of time coefficient m of each points. By improving as above, the algorithm can be adapted to trajectory datasampled at unequal time intervals. In addition, when searching for the field of points, it is not necessary to search theentire set of trajectory points, but only need to start with the center point, and search forward and backward until thedistance between the two points is greater than the threshold ε.</p><p>(3)Improvement of clustering order method: When generating the clustering order, the OPTICS needs to center thecurrent point in order, and correct the reachable distance value of each point in the ε neighborhood of the point, then thepoint at the minimum distance is selected as the subsequent point. For the trajectory data, the subsequent point on thetrajectory is obviously the point which the reachable distance is the shortest in the ε neighborhood of the current point,and so the clustering order is consistent with the trajectory points sequence. Therefore, the improved algorithm only needsto calculate the reachable distance of a subsequent point of the current point, thereby quickly generating a clusteringsequence.</p><p>(4)The scale of the staying feature is automatically controlled by reachable distance. Although the OPTICS is capableof generating multi-level clustering results, it does not measure the hierarchy. In this paper, the scale of each stay featureis measured by the reachable distance range of a cluster, and the relationship between the reachable distance and the stayfeature scale is established, so that the multi-scale stay feature can be obtained automatically.</p><p>This paper compares this method with other methods using a variety of trajectory data. The results show that the method can extract the track stay feature faster and more accurately, and can automatically control the stay feature extraction level.</p>

To operate with limited sensor horizons in unpredictable environments, autonomous robots use a receding-horizon strategy to plan trajectories, wherein they execute a short plan while creating the next plan. However, creating safe, dynamically feasible trajectories in real time is challenging, and planners must ensure persistent feasibility, meaning a new trajectory is always available before the previous one has finished executing. Existing approaches make a tradeoff between model complexity and planning speed, which can require sacrificing guarantees of safety and dynamic feasibility. This work presents the Reachability-based Trajectory Design (RTD) method for trajectory planning. RTD begins with an offline forward reachable set (FRS) computation of a robot’s motion when tracking parameterized trajectories; the FRS provably bounds tracking error. At runtime, the FRS is used to map obstacles to parameterized trajectories, allowing RTD to select a safe trajectory at every planning iteration. RTD prescribes an obstacle representation to ensure that obstacle constraints can be created and evaluated in real time while maintaining safety. Persistent feasibility is achieved by prescribing a minimum sensor horizon and a minimum duration for the planned trajectories. A system decomposition approach is used to improve the tractability of computing the FRS, allowing RTD to create more complex plans at runtime. RTD is compared in simulation with rapidly-exploring random trees and nonlinear model-predictive control. RTD is also demonstrated in randomly crafted environments on two hardware platforms: a differential-drive Segway and a car-like Rover. The proposed method is safe and persistently feasible across thousands of simulations and dozens of real-world hardware demos.

In recent years, there is a growing awareness of the importance of reachability and relevance-based pruning techniques for planning, but little work specifically targets these techniques. In this paper, we compare the ability of two classes of algorithms to propagate and discover reachability and relevance constraints in classical planning problems. The first class of algorithms operates on SAT encoded planning problems obtained using the linear and Graphplan encoding schemes. It applies unit-propagation and more general resolution steps (involving larger clauses) to these plan encodings. The second class operates at the plan level and contains two families of pruning algorithms: Reachable-k and Relevant-k. Reachable-k provides a coherent description of a number of existing forward pruning techniques used in numerous algorithms, while Relevant-k captures different grades of backward pruning. Our results shed light on the ability of different plan-encoding schemes to propagate information forward and backward and on the relative merit of plan-level and SAT-level pruning methods.

This paper proposes the design of a novel 3-DOF monolithic manipulator. This manipulator is capable of performing planar manipulations with three kinematically coupled DOFs, i.e., the translations in the X and Y axes and the rotation about the Z axis. An improved Scott-Russell (ISR) mechanism is utilized to magnify the displacement of the piezoelectric actuator (PEA). Unlike the SR mechanism, a set of leaf parallelograms is incorporated into the drive point of the ISR mechanism as a prismatic joint. As a result, the linearity of motion and stability are improved. With circular flexure hinges being treated as revolute joints, the forward kinematics and inverse kinematics of the 3-DOF manipulator are analytically derived. Computational analyses are performed to validate the established kinematics models. Due to the unwanted compliance of the flexure hinges, the actual displacement amplification ratio of the ISR mechanism is smaller than its theoretical value. This is the main cause of the discrepancies between the analytical and computational results. The reachable workspace and the static/dynamic characteristics of the 3-DOF manipulator are also analyzed.

AbstractWe study the reachability problem for queue automata and lossy queue automata. Concretely, we consider the set of queue contents which are forwards resp. backwards reachable from a given set of queue contents. Here, we prove the preservation of regularity if the queue automaton loops through some special sets of transformation sequences. This is a generalization of the results by Boigelot et al. and Abdulla et al. regarding queue automata looping through a single sequence of transformations. We also prove that our construction is possible in polynomial time.