A privacy-preserving model for multi-agent propositional planning

Abstract

Over the last years, the planning community has formalised several models and approaches to multi-agent (MA) propositional planning. One of the main motivations in MA planning is that some or all agents have private knowledge that cannot be communicated to other agents during the planning process and the plan execution. We argue that the existing models of the multi-agent planning task do not maintain the agents’ privacy when a (strict) subset of the involved agents share confidential knowledge, or when the identity/existence of at least one agent is confidential. In this paper, first we propose a model of the MA-planning tasks that preserves the privacy of the involved agents when this happens. Then we investigate an algorithm based on best first search for our model that uses some new heuristics providing a trade-off between accuracy and agents’ privacy. Finally, an experimental study compares the effectiveness of using the proposed heuristics.     

Decision-theoretic planning with generalized first-order decision diagrams

Many tasks in AI require representation and manipulation of complex functions. First-Order Decision Diagrams (FODD) are a compact knowledge representation expressing functions over relational structures. They represent numerical functions that, when constrained to the Boolean range, use only existential quantification. Previous work has developed a set of operations for composition and for removing redundancies in FODDs, thus keeping them compact, and showed how to successfully employ FODDs for solving large-scale stochastic planning problems through the formalism of relational Markov decision processes (RMDP). In this paper, we introduce several new ideas enhancing the applicability of FODDs. More specifically, we first introduce Generalized FODDs (GFODD) and composition operations for them, generalizing FODDs to arbitrary quantification. Second, we develop a novel approach for reducing (G)FODDs using model checking. This yields – for the first time – a reduction that maximally reduces the diagram for the FODD case and provides a sound reduction procedure for GFODDs. Finally we show how GFODDs can be used in principle to solve RMDPs with arbitrary quantification, and develop a complete solution for the case where the reward function is specified using an arbitrary number of existential quantifiers followed by an arbitrary number of universal quantifiers.     

Formal design and verification of operational transformation algorithms for copies convergence

Distributed groupware systems provide computer support for manipulating objects such as a text document or a filesystem, shared by two or more geographically separated users. Data replication is a technology to improve performance and availability of data in distributed groupware systems. Indeed, each user has a local copy of the shared objects, upon which he may perform updates. Locally executed updates are then transmitted to the other users. This replication potentially leads, however, to divergent (i.e. different) copies. In this respect, Operational Transformation (OT) algorithms are applied for achieving convergence of all copies, i.e. all users view the same objects. Using these algorithms users can exchange their updates in any order since the convergence should be ensured in all cases. However, the design of such algorithms is a difficult and error-prone activity since building the correct updates for maintaining good convergence properties of the local copies requires examining a large number of situations. In this paper, we present the modelling and deductive verification of OT algorithms with algebraic specifications. We show in particular that many OT algorithms in the literature do not satisfy convergence properties unlike what was stated by their authors.     

Optimum motion planning in joint space for robots using genetic algorithms

The optimum motion planning in joint space (OMPJS) for robots, which generally consists of two subproblems, optimum path planning and optimum trajectory planning, was considered as a whole in the paper. A new method for optimum motion planning problem based on an improved genetic algorithm is proposed, which is more general, flexible and effective. This approach incorporates kinematics constraints, dynamics constraints, and control constraints of robotic manipulator. The simulation results for a two and a three degrees of freedom robots are presented and discussed. The simulations are based on genetic algorithm class library WGAClass 1.0 developed by us with Borland C++ 3.1.     

An integral theorem prover and the role of proof planning

An investigation is made into the ways proof planning can enhance the capability of a rule based prover for the theory of integration. The integrals are of the Riemann type and are defined in a way to maximize the theorem proving methods of predicate calculus. Approximately fifty theorems have been proved and several examples are discussed. A major shortcoming was found to be the inability of the system to work with or produce a proof plan. As a result, a planning scheme based on the idea of subgoals or milestones was considered. With user defined plans, there was a substantial increase in performance and capability of the system and, in some cases, proofs which were previously unsuccessful were completed.     

Operations planning for collect-and-place machines in PCB assembly

Collect-and-place machines represent one of the most popular types of placement machines in automated printed circuit board (PCB) assembly. For scheduling the operations of this type of machinery, a three-stage heuristic solution approach is presented. In the first stage, the feeders (component types) are assigned to locations in the magazine of the placement machine. In the second stage, based on the assignment of component feeders to magazine positions, the component placement sequence is determined. Apparently, for a collect-and-place machine, this problem is similar to the well-known vehicle-routing problem. Therefore, we adapt standard methods for vehicle-routing problems, namely savings heuristics introduced by Clark and Wright [Clark, G., & Wright, J. W. (1964). Scheduling vehicles from a central delivery depot to a number of delivery points. Operations Research Quarterly, 12, 568–581]. Finally, local search principles are applied in order to improve the feeder assignment and the component placement sequence obtained. Numerical experiments are performed in order to compare the performance of the various savings-based heuristics under different experimental settings.     

一种移动机器人路径规划新算法

快速搜索随机树（Rapidly-exploring random Tree Star,RRT*）算法在移动机器人实际应用中规划路径在转向部分存在较多的冗余转折点,导致移动机器人在移动转向过程中出现多次停顿与转向,为剔除规划路径中的冗余路径点,提高机器人移动流畅性,提出一种改进的 RRT*算法。算法将局部逆序试连法引入移动机器人路径规划,在确保RRT*算法概率完备性和渐进最优性的前提下,剔除规划路径中的冗余路径节点,使最终路径更加接近最短路径。通过MATLAB仿真实验证明,规划路径平均长度缩短4%,算法耗时缩短35%,改进后的RRT*算法能缩短规划路径且转向部分路径更加平滑。最后,使用改进后的RRT*算法在室内环境下进行移动机器人路径规划实验。实验结果表明：规划路径上无冗余路径点,且移动机器人沿路径移动流畅。     

The path and location planning of workpieces by genetic algorithms

This paper presents the planning of a near-optimum path and location of a workpiece by genetic algorithms. The purpose of this planning is to minimize the processing time required for a robot to complete its work on a workpiece. The location of the workpiece can be anywhere by translating it along any direction and by rotating it about the fixedz-axis of the robot coordinate system. Owing to the changeable location of the workpiece and the alterable motion time required for a robot to move between two workpoints, the path and location planning problem is much more complicated than the travelling salesman problem. It is definitely impossible to obtain an optimum path and location within an acceptable time. In this paper, genetic algorithms are applied to solve this problem. The location of the workpiece is defined by three position parameters and one angular parameter, and the path is determined based on the values of the parameters for all workpoints. All the path and location parameters are encoded into a binary string. They are modified simultaneously by genetic algorithms to search for a global solution. As the workpiece can be anywhere, a penalty function is used to prevent the selection of illegal paths. Two experiments are given to show the performance of genetic algorithms: one has 30 workpoints and the other has 50 workpoints. Compared with four human-generated plannings, planning by genetic algorithms has much better performance in minimizing the processing time.     

A new model for path planning with interval data

In this paper, we establish a new model for path planning with interval data which arises in a variety of applications. It is formulated as minimum risk-sum path problem  : given a source-destination pair in a network G=(V,E)$G=(V,E)$, traveling on each link e in G   may take time _xe$x_e$ in a prespecified interval [_le,_ue]$[l_e,u_e]$ and take risk (_ue-_xe)/(_ue-_le)$(u_e-x_e)/(u_e-l_e)$, the goal is to find a path in G from the source to the destination, together with an allocation of travel times along each link on the path, so that the total travel time of links on the path is no more than a given time bound and the risk-sum over the links on the path is minimized. Our study shows that this new model has two features that make it different from the existing models. First, the minimum risk-sum path problem is polynomial-time solvable, and second, it provides many solutions that vary with time bounds and risk sums and leaves the choice for decision makers. Therefore, the new model is more flexible and easier to use for the path planning with interval data.     

Genetic algorithms in integrated process planning and scheduling

Process planning and scheduling are actually interrelated and should be solved simultaneously. Most integrated process planning and scheduling methods only consider the time aspects of the alternative machines when constructing schedules. The initial part of this paper describes a genetic algorithm (GA) based algorithm that only considers the time aspect of the alternative machines. The scope of consideration is then further extended to include the processing capabilities of alternative machines, with different tolerance limits and processing costs. In the proposed method based on GAs, the processing capabilities of the machines, including processing costs as well as number of rejects produced in alternative machine are considered simultaneously with the scheduling of jobs. The formulation is based on multi-objective weighted-sums optimization, which are to minimize makespan, to minimize total rejects produced and to minimize the total cost of production. A comparison is done w ith the traditional sequential method and the multi-objective genetic algorithm (MOGA) approach, based on the Pareto optimal concept.     

Experimental validation and comparative analysis of optimal time-jerk algorithms for trajectory planning

In this paper, two minimum time-jerk trajectory planning algorithms for robotic manipulators have been considered, evaluated and experimentally validated. These algorithms consider both the execution time and the integral of the squared jerk along the whole trajectory, so as to take into account the need for fast execution and the need for a smooth trajectory, by adjusting the values of two weights. A comparative analysis of these algorithms with two different trajectory planning techniques taken from the literature has been carried out, by means of experimental tests performed on a real robotic manipulator. The results prove the experimental effectiveness of the proposed techniques.     

Automated instructional design for CSCL: A hierarchical task network planning approach

In Computer Supported Collaborative Learning (CSCL), one of the most important tasks for instructional designers is to define scenarios that foster group learning. Such scenarios, defined as Units of Learning (UoLs), comprise different components and are organized according to pedagogical approaches to orchestrate group learning processes. Examples of UoL components are learning objects, student roles, student characteristics (e.g., background, preferences, learning styles, etc.), instructional/learning goals, and activities, among others. Thus, the instructional design (ID) of a proper UoL for CSCL is a complex task that requires practice and experience. This is particularly true when designing, developing, adapting, and customizing UoLs, taking into consideration different instructional/learning goals and individual preferences of students. This paper therefore proposes using a Hierarchical Task Network (HTN) planning approach to automate and optimize the tasks of designers. To accomplish that, we define an initial CSCL scenario as “an ID task” and “a set of information related to students and the domain to be taught.” Then we propose a model that formally describes ID for CSCL as HTN planning, where the initial CSCL scenario is adapted and refined according to student needs. In this model, the ID strategies are defined as hierarchical tasks and methods into a planning domain definition, and the initial CSCL scenario is defined as a planning problem definition. To validate our approach, we develop a CSCL courseware generator that (i) helps designers to set up an initial CSCL scenario; (ii) automatically generates a personalized UoL based on a given initial scenario; and (iii) supports the adaptation of UoLs.     

A symbolic framework for multi-faceted security protocol analysis

Verification of software systems, and security protocol analysis as a particular case, requires frameworks that are expressive, so as to properly capture the relevant aspects of the system and its properties, formal, so as to be provably correct, and with a computational counterpart, so as to support the (semi-) automated certification of properties. Additionally, security protocols also present hidden assumptions about the context, specific subtleties due to the nature of the problem and sources of complexity that tend to make verification incomplete. We introduce a verification framework that is expressive enough to capture a few relevant aspects of the problem, like symmetric and asymmetric cryptography and multi-session analysis, and to make assumptions explicit, e.g., the hypotheses about the initial sharing of secret keys among honest (and malicious) participants. It features a clear separation between the modeling of the protocol functioning and the properties it is expected to enforce, the former in terms of a calculus, the latter in terms of a logic. This framework is grounded on a formal theory that allows us to prove the correctness of the verification carried out within the fully fledged model. It overcomes incompleteness by performing the analysis at a symbolic level of abstraction, which, moreover, transforms into executable verification tools.     

融合改进A*算法和Morphin算法的移动机器人动态路径规划

在动态未知环境下对机器人进行路径规划,传统A*算法可能出现碰撞或者路径规划失败问题。为了满足移动机器人全局路径规划最优和实时避障的需求,提出一种改进A*算法与Morphin搜索树算法相结合的动态路径规划方法。首先通过改进A*算法减少路径规划过程中关键节点的选取,在规划出一条全局较优路径的同时对路径平滑处理。然后基于移动机器人传感器采集的局部信息,利用Morphin搜索树算法对全局路径进行动态的局部规划,确保更好的全局路径的基础上,实时避开障碍物行驶到目标点。MATLAB仿真实验结果表明,提出的动态路径规划方法在时间和路径上得到提升,在优化全局路径规划的基础上修正局部路径,实现动态避障提高机器人达到目标点的效率。     

广义Birkhoff系统的梯度表示

研究广义 Birkhoff 系统的梯度表示. 给出广义 Birkhoff 系统可成为梯度系统的条件. 利用梯度系统的性质来研究广义 Birkhoff 系统的稳定性. 举例说明结果的应用.     

Interference probability matrix for disassembly sequence planning under uncertain interference

Disassembly of end-of-life products is a common step in remanufacturing and recycling. Disassembly sequence planning is the process that automatically finds the optimal sequence of components being removed. A key element of disassembly sequence planning is a suitable mathematical representation that describes the interference of any two components in a product. Previous studies on disassembly sequence planning have tended to focused on the interference that is fixed and known. However, the interference may be uncertain due to complex end-of-life conditions such as deformation, corrosion and rust. To deal with uncertain interference, this paper proposes an interference probability matrix as a new mathematical representation that uses probability to indicate uncertainty in the interference, and establishes a multi-threshold planning scheme to generate the optimal disassembly sequence plans. Three case studies are given to demonstrate the use of the proposed approach. It is also tested the performance of four multi-objective optimization algorithms that can be adopted in the proposed multi-threshold planning scheme.     

融合强化学习和进化算法的高超声速飞行器航迹规划

由于高超声速飞行器的复杂特性,对其进行航迹规划是一项非常困难的任务.本文针对高超声速飞行器巡航段,提出了一种将无模型的强化学习和交叉熵方法相结合的在线航迹规划算法.本文将航迹规划问题建模为环境信息缺失程度不同的马尔可夫决策过程,利用(PPO)算法在建立的飞行环境模拟器中离线训练智能体,并通过提高智能体的动作在时间上的相关性来保证航迹的曲率平滑.交叉熵方法则以已训练的智能体由观测到的状态给出的动作作为一种先验知识,进一步在线优化规划策略.实验结果表明了本文的方法可以生成曲率平滑的航迹,在复杂的飞行环境中具有较高的成功率,并且可以泛化到不同的飞行环境中.     

动态未知环境下一种新的机器人路径规划方法

针对机器人动态路径规划问题,提出了一种机器人在复杂动态环境中实时路径规划方法.该方法基于滚动窗口的路径规划和避障策略,通过设定可视点子目标、绕行障碍物和对动态障碍物的分析预测,实现机器人在复杂动态环境下的路径规划.针对障碍物分布情况,合理设计可视点法和绕行算法之间转换,有效地解决了局部路径规划的死循环与极小值问题.该方...