Robust switching of discrete-time switched linear systems

Recent Advances in Robust Optimization and Robustness:An OverviewVirginie Gabrel∗and C´e cile Murat†and Aur´e lie Thiele‡July2012AbstractThis paper provides an overview of developments in robust optimization and robustness published in the aca-demic literature over the pastfive years.1IntroductionThis review focuses on papers identified by Web of Science as having been published since2007(included),be-longing to the area of Operations Research and Management Science,and having‘robust’and‘optimization’in their title.There were exactly100such papers as of June20,2012.We have completed this list by considering 726works indexed by Web of Science that had either robustness(for80of them)or robust(for646)in their title and belonged to the Operations Research and Management Science topic area.We also identified34PhD disserta-tions dated from the lastfive years with‘robust’in their title and belonging to the areas of operations research or management.Among those we have chosen to focus on the works with a primary focus on management science rather than system design or optimal control,which are broadfields that would deserve a review paper of their own, and papers that could be of interest to a large segment of the robust optimization research community.We feel it is important to include PhD dissertations to identify these recent graduates as the new generation trained in robust optimization and robustness analysis,whether they have remained in academia or joined industry.We have also added a few not-yet-published preprints to capture ongoing research efforts.While many additional works would have deserved inclusion,we feel that the works selected give an informative and comprehensive view of the state of robustness and robust optimization to date in the context of operations research and management science.∗Universit´e Paris-Dauphine,LAMSADE,Place du Mar´e chal de Lattre de Tassigny,F-75775Paris Cedex16,France gabrel@lamsade.dauphine.fr Corresponding author†Universit´e Paris-Dauphine,LAMSADE,Place du Mar´e chal de Lattre de Tassigny,F-75775Paris Cedex16,France mu-rat@lamsade.dauphine.fr‡Lehigh University,Industrial and Systems Engineering Department,200W Packer Ave Bethlehem PA18015,USA aure-lie.thiele@2Theory of Robust Optimization and Robustness2.1Definitions and BasicsThe term“robust optimization”has come to encompass several approaches to protecting the decision-maker against parameter ambiguity and stochastic uncertainty.At a high level,the manager must determine what it means for him to have a robust solution:is it a solution whose feasibility must be guaranteed for any realization of the uncertain parameters?or whose objective value must be guaranteed?or whose distance to optimality must be guaranteed? The main paradigm relies on worst-case analysis:a solution is evaluated using the realization of the uncertainty that is most unfavorable.The way to compute the worst case is also open to debate:should it use afinite number of scenarios,such as historical data,or continuous,convex uncertainty sets,such as polyhedra or ellipsoids?The answers to these questions will determine the formulation and the type of the robust counterpart.Issues of over-conservatism are paramount in robust optimization,where the uncertain parameter set over which the worst case is computed should be chosen to achieve a trade-off between system performance and protection against uncertainty,i.e.,neither too small nor too large.2.2Static Robust OptimizationIn this framework,the manager must take a decision in the presence of uncertainty and no recourse action will be possible once uncertainty has been realized.It is then necessary to distinguish between two types of uncertainty: uncertainty on the feasibility of the solution and uncertainty on its objective value.Indeed,the decision maker generally has different attitudes with respect to infeasibility and sub-optimality,which justifies analyzing these two settings separately.2.2.1Uncertainty on feasibilityWhen uncertainty affects the feasibility of a solution,robust optimization seeks to obtain a solution that will be feasible for any realization taken by the unknown coefficients;however,complete protection from adverse realiza-tions often comes at the expense of a severe deterioration in the objective.This extreme approach can be justified in some engineering applications of robustness,such as robust control theory,but is less advisable in operations research,where adverse events such as low customer demand do not produce the high-profile repercussions that engineering failures–such as a doomed satellite launch or a destroyed unmanned robot–can have.To make the robust methodology appealing to business practitioners,robust optimization thus focuses on obtaining a solution that will be feasible for any realization taken by the unknown coefficients within a smaller,“realistic”set,called the uncertainty set,which is centered around the nominal values of the uncertain parameters.The goal becomes to optimize the objective,over the set of solutions that are feasible for all coefficient values in the uncertainty set.The specific choice of the set plays an important role in ensuring computational tractability of the robust problem and limiting deterioration of the objective at optimality,and must be thought through carefully by the decision maker.A large branch of robust optimization focuses on worst-case optimization over a convex uncertainty set.The reader is referred to Bertsimas et al.(2011a)and Ben-Tal and Nemirovski(2008)for comprehensive surveys of robust optimization and to Ben-Tal et al.(2009)for a book treatment of the topic.2.2.2Uncertainty on objective valueWhen uncertainty affects the optimality of a solution,robust optimization seeks to obtain a solution that performs well for any realization taken by the unknown coefficients.While a common criterion is to optimize the worst-case objective,some studies have investigated other robustness measures.Roy(2010)proposes a new robustness criterion that holds great appeal for the manager due to its simplicity of use and practical relevance.This framework,called bw-robustness,allows the decision-maker to identify a solution which guarantees an objective value,in a maximization problem,of at least w in all scenarios,and maximizes the probability of reaching a target value of b(b>w).Gabrel et al.(2011)extend this criterion from afinite set of scenarios to the case of an uncertainty set modeled using intervals.Kalai et al.(2012)suggest another criterion called lexicographicα-robustness,also defined over afinite set of scenarios for the uncertain parameters,which mitigates the primary role of the worst-case scenario in defining the solution.Thiele(2010)discusses over-conservatism in robust linear optimization with cost uncertainty.Gancarova and Todd(2012)studies the loss in objective value when an inaccurate objective is optimized instead of the true one, and shows that on average this loss is very small,for an arbitrary compact feasible region.In combinatorial optimization,Morrison(2010)develops a framework of robustness based on persistence(of decisions)using the Dempster-Shafer theory as an evidence of robustness and applies it to portfolio tracking and sensor placement.2.2.3DualitySince duality has been shown to play a key role in the tractability of robust optimization(see for instance Bertsimas et al.(2011a)),it is natural to ask how duality and robust optimization are connected.Beck and Ben-Tal(2009) shows that primal worst is equal to dual best.The relationship between robustness and duality is also explored in Gabrel and Murat(2010)when the right-hand sides of the constraints are uncertain and the uncertainty sets are represented using intervals,with a focus on establishing the relationships between linear programs with uncertain right hand sides and linear programs with uncertain objective coefficients using duality theory.This avenue of research is further explored in Gabrel et al.(2010)and Remli(2011).2.3Multi-Stage Decision-MakingMost early work on robust optimization focused on static decision-making:the manager decided at once of the values taken by all decision variables and,if the problem allowed for multiple decision stages as uncertainty was realized,the stages were incorporated by re-solving the multi-stage problem as time went by and implementing only the decisions related to the current stage.As thefield of static robust optimization matured,incorporating–ina tractable manner–the information revealed over time directly into the modeling framework became a major area of research.2.3.1Optimal and Approximate PoliciesA work going in that direction is Bertsimas et al.(2010a),which establishes the optimality of policies affine in the uncertainty for one-dimensional robust optimization problems with convex state costs and linear control costs.Chen et al.(2007)also suggests a tractable approximation for a class of multistage chance-constrained linear program-ming problems,which converts the original formulation into a second-order cone programming problem.Chen and Zhang(2009)propose an extension of the Affinely Adjustable Robust Counterpart framework described in Ben-Tal et al.(2009)and argue that its potential is well beyond what has been in the literature so far.2.3.2Two stagesBecause of the difficulty in incorporating multiple stages in robust optimization,many theoretical works have focused on two stages.Regarding two-stage problems,Thiele et al.(2009)presents a cutting-plane method based on Kelley’s algorithm for solving convex adjustable robust optimization problems,while Terry(2009)provides in addition preliminary results on the conditioning of a robust linear program and of an equivalent second-order cone program.Assavapokee et al.(2008a)and Assavapokee et al.(2008b)develop tractable algorithms in the case of robust two-stage problems where the worst-case regret is minimized,in the case of interval-based uncertainty and scenario-based uncertainty,respectively,while Minoux(2011)provides complexity results for the two-stage robust linear problem with right-hand-side uncertainty.2.4Connection with Stochastic OptimizationAn early stream in robust optimization modeled stochastic variables as uncertain parameters belonging to a known uncertainty set,to which robust optimization techniques were then applied.An advantage of this method was to yield approaches to decision-making under uncertainty that were of a level of complexity similar to that of their deterministic counterparts,and did not suffer from the curse of dimensionality that afflicts stochastic and dynamic programming.Researchers are now making renewed efforts to connect the robust optimization and stochastic opti-mization paradigms,for instance quantifying the performance of the robust optimization solution in the stochastic world.The topic of robust optimization in the context of uncertain probability distributions,i.e.,in the stochastic framework itself,is also being revisited.2.4.1Bridging the Robust and Stochastic WorldsBertsimas and Goyal(2010)investigates the performance of static robust solutions in two-stage stochastic and adaptive optimization problems.The authors show that static robust solutions are good-quality solutions to the adaptive problem under a broad set of assumptions.They provide bounds on the ratio of the cost of the optimal static robust solution to the optimal expected cost in the stochastic problem,called the stochasticity gap,and onthe ratio of the cost of the optimal static robust solution to the optimal cost in the two-stage adaptable problem, called the adaptability gap.Chen et al.(2007),mentioned earlier,also provides a robust optimization perspective to stochastic programming.Bertsimas et al.(2011a)investigates the role of geometric properties of uncertainty sets, such as symmetry,in the power offinite adaptability in multistage stochastic and adaptive optimization.Duzgun(2012)bridges descriptions of uncertainty based on stochastic and robust optimization by considering multiple ranges for each uncertain parameter and setting the maximum number of parameters that can fall within each range.The corresponding optimization problem can be reformulated in a tractable manner using the total unimodularity of the feasible set and allows for afiner description of uncertainty while preserving tractability.It also studies the formulations that arise in robust binary optimization with uncertain objective coefficients using the Bernstein approximation to chance constraints described in Ben-Tal et al.(2009),and shows that the robust optimization problems are deterministic problems for modified values of the coefficients.While many results bridging the robust and stochastic worlds focus on giving probabilistic guarantees for the solutions generated by the robust optimization models,Manuja(2008)proposes a formulation for robust linear programming problems that allows the decision-maker to control both the probability and the expected value of constraint violation.Bandi and Bertsimas(2012)propose a new approach to analyze stochastic systems based on robust optimiza-tion.The key idea is to replace the Kolmogorov axioms and the concept of random variables as primitives of probability theory,with uncertainty sets that are derived from some of the asymptotic implications of probability theory like the central limit theorem.The authors show that the performance analysis questions become highly structured optimization problems for which there exist efficient algorithms that are capable of solving problems in high dimensions.They also demonstrate that the proposed approach achieves computationally tractable methods for(a)analyzing queueing networks,(b)designing multi-item,multi-bidder auctions with budget constraints,and (c)pricing multi-dimensional options.2.4.2Distributionally Robust OptimizationBen-Tal et al.(2010)considers the optimization of a worst-case expected-value criterion,where the worst case is computed over all probability distributions within a set.The contribution of the work is to define a notion of robustness that allows for different guarantees for different subsets of probability measures.The concept of distributional robustness is also explored in Goh and Sim(2010),with an emphasis on linear and piecewise-linear decision rules to reformulate the original problem in aflexible manner using expected-value terms.Xu et al.(2012) also investigates probabilistic interpretations of robust optimization.A related area of study is worst-case optimization with partial information on the moments of distributions.In particular,Popescu(2007)analyzes robust solutions to a certain class of stochastic optimization problems,using mean-covariance information about the distributions underlying the uncertain parameters.The author connects the problem for a broad class of objective functions to a univariate mean-variance robust objective and,subsequently, to a(deterministic)parametric quadratic programming problem.The reader is referred to Doan(2010)for a moment-based uncertainty model for stochastic optimization prob-lems,which addresses the ambiguity of probability distributions of random parameters with a minimax decision rule,and a comparison with data-driven approaches.Distributionally robust optimization in the context of data-driven problems is the focus of Delage(2009),which uses observed data to define a”well structured”set of dis-tributions that is guaranteed with high probability to contain the distribution from which the samples were drawn. Zymler et al.(2012a)develop tractable semidefinite programming(SDP)based approximations for distributionally robust individual and joint chance constraints,assuming that only thefirst-and second-order moments as well as the support of the uncertain parameters are given.Becker(2011)studies the distributionally robust optimization problem with known mean,covariance and support and develops a decomposition method for this family of prob-lems which recursively derives sub-policies along projected dimensions of uncertainty while providing a sequence of bounds on the value of the derived policy.Robust linear optimization using distributional information is further studied in Kang(2008).Further,Delage and Ye(2010)investigates distributional robustness with moment uncertainty.Specifically,uncertainty affects the problem both in terms of the distribution and of its moments.The authors show that the resulting problems can be solved efficiently and prove that the solutions exhibit,with high probability,best worst-case performance over a set of distributions.Bertsimas et al.(2010)proposes a semidefinite optimization model to address minimax two-stage stochastic linear problems with risk aversion,when the distribution of the second-stage random variables belongs to a set of multivariate distributions with knownfirst and second moments.The minimax solutions provide a natural distribu-tion to stress-test stochastic optimization problems under distributional ambiguity.Cromvik and Patriksson(2010a) show that,under certain assumptions,global optima and stationary solutions of stochastic mathematical programs with equilibrium constraints are robust with respect to changes in the underlying probability distribution.Works such as Zhu and Fukushima(2009)and Zymler(2010)also study distributional robustness in the context of specific applications,such as portfolio management.2.5Connection with Risk TheoryBertsimas and Brown(2009)describe how to connect uncertainty sets in robust linear optimization to coherent risk measures,an example of which is Conditional Value-at-Risk.In particular,the authors show the link between polyhedral uncertainty sets of a special structure and a subclass of coherent risk measures called distortion risk measures.Independently,Chen et al.(2007)present an approach for constructing uncertainty sets for robust opti-mization using new deviation measures that capture the asymmetry of the distributions.These deviation measures lead to improved approximations of chance constraints.Dentcheva and Ruszczynski(2010)proposes the concept of robust stochastic dominance and shows its applica-tion to risk-averse optimization.They consider stochastic optimization problems where risk-aversion is expressed by a robust stochastic dominance constraint and develop necessary and sufficient conditions of optimality for such optimization problems in the convex case.In the nonconvex case,they derive necessary conditions of optimality under additional smoothness assumptions of some mappings involved in the problem.2.6Nonlinear OptimizationRobust nonlinear optimization remains much less widely studied to date than its linear counterpart.Bertsimas et al.(2010c)presents a robust optimization approach for unconstrained non-convex problems and problems based on simulations.Such problems arise for instance in the partial differential equations literature and in engineering applications such as nanophotonic design.An appealing feature of the approach is that it does not assume any specific structure for the problem.The case of robust nonlinear optimization with constraints is investigated in Bertsimas et al.(2010b)with an application to radiation therapy for cancer treatment.Bertsimas and Nohadani (2010)further explore robust nonconvex optimization in contexts where solutions are not known explicitly,e.g., have to be found using simulation.They present a robust simulated annealing algorithm that improves performance and robustness of the solution.Further,Boni et al.(2008)analyzes problems with uncertain conic quadratic constraints,formulating an approx-imate robust counterpart,and Zhang(2007)provide formulations to nonlinear programming problems that are valid in the neighborhood of the nominal parameters and robust to thefirst order.Hsiung et al.(2008)present tractable approximations to robust geometric programming,by using piecewise-linear convex approximations of each non-linear constraint.Geometric programming is also investigated in Shen et al.(2008),where the robustness is injected at the level of the algorithm and seeks to avoid obtaining infeasible solutions because of the approximations used in the traditional approach.Interval uncertainty-based robust optimization for convex and non-convex quadratic programs are considered in Li et al.(2011).Takeda et al.(2010)studies robustness for uncertain convex quadratic programming problems with ellipsoidal uncertainties and proposes a relaxation technique based on random sampling for robust deviation optimization sserre(2011)considers minimax and robust models of polynomial optimization.A special case of nonlinear problems that are linear in the decision variables but convex in the uncertainty when the worst-case objective is to be maximized is investigated in Kawas and Thiele(2011a).In that setting,exact and tractable robust counterparts can be derived.A special class of nonconvex robust optimization is examined in Kawas and Thiele(2011b).Robust nonconvex optimization is examined in detail in Teo(2007),which presents a method that is applicable to arbitrary objective functions by iteratively moving along descent directions and terminates at a robust local minimum.3Applications of Robust OptimizationWe describe below examples to which robust optimization has been applied.While an appealing feature of robust optimization is that it leads to models that can be solved using off-the-shelf software,it is worth pointing the existence of algebraic modeling tools that facilitate the formulation and subsequent analysis of robust optimization problems on the computer(Goh and Sim,2011).3.1Production,Inventory and Logistics3.1.1Classical logistics problemsThe capacitated vehicle routing problem with demand uncertainty is studied in Sungur et al.(2008),with a more extensive treatment in Sungur(2007),and the robust traveling salesman problem with interval data in Montemanni et al.(2007).Remli and Rekik(2012)considers the problem of combinatorial auctions in transportation services when shipment volumes are uncertain and proposes a two-stage robust formulation solved using a constraint gener-ation algorithm.Zhang(2011)investigates two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty,in particular showing that it is polynomially solvable under the interval uncertain demand set.3.1.2SchedulingGoren and Sabuncuoglu(2008)analyzes robustness and stability measures for scheduling in a single-machine environment subject to machine breakdowns and embeds them in a tabu-search-based scheduling algorithm.Mittal (2011)investigates efficient algorithms that give optimal or near-optimal solutions for problems with non-linear objective functions,with a focus on robust scheduling and service operations.Examples considered include parallel machine scheduling problems with the makespan objective,appointment scheduling and assortment optimization problems with logit choice models.Hazir et al.(2010)considers robust scheduling and robustness measures for the discrete time/cost trade-off problem.3.1.3Facility locationAn important question in logistics is not only how to operate a system most efficiently but also how to design it. Baron et al.(2011)applies robust optimization to the problem of locating facilities in a network facing uncertain demand over multiple periods.They consider a multi-periodfixed-charge network location problem for which they find the number of facilities,their location and capacities,the production in each period,and allocation of demand to facilities.The authors show that different models of uncertainty lead to very different solution network topologies, with the model with box uncertainty set opening fewer,larger facilities.?investigate a robust version of the location transportation problem with an uncertain demand using a2-stage formulation.The resulting robust formulation is a convex(nonlinear)program,and the authors apply a cutting plane algorithm to solve the problem exactly.Atamt¨u rk and Zhang(2007)study the networkflow and design problem under uncertainty from a complexity standpoint,with applications to lot-sizing and location-transportation problems,while Bardossy(2011)presents a dual-based local search approach for deterministic,stochastic,and robust variants of the connected facility location problem.The robust capacity expansion problem of networkflows is investigated in Ordonez and Zhao(2007),which provides tractable reformulations under a broad set of assumptions.Mudchanatongsuk et al.(2008)analyze the network design problem under transportation cost and demand uncertainty.They present a tractable approximation when each commodity only has a single origin and destination,and an efficient column generation for networks with path constraints.Atamt¨u rk and Zhang(2007)provides complexity results for the two-stage networkflow anddesign plexity results for the robust networkflow and network design problem are also provided in Minoux(2009)and Minoux(2010).The problem of designing an uncapacitated network in the presence of link failures and a competing mode is investigated in Laporte et al.(2010)in a railway application using a game theoretic perspective.Torres Soto(2009)also takes a comprehensive view of the facility location problem by determining not only the optimal location but also the optimal time for establishing capacitated facilities when demand and cost parameters are time varying.The models are solved using Benders’decomposition or heuristics such as local search and simulated annealing.In addition,the robust networkflow problem is also analyzed in Boyko(2010),which proposes a stochastic formulation of minimum costflow problem aimed atfinding network design andflow assignments subject to uncertain factors,such as network component disruptions/failures when the risk measure is Conditional Value at Risk.Nagurney and Qiang(2009)suggests a relative total cost index for the evaluation of transportation network robustness in the presence of degradable links and alternative travel behavior.Further,the problem of locating a competitive facility in the plane is studied in Blanquero et al.(2011)with a robustness criterion.Supply chain design problems are also studied in Pan and Nagi(2010)and Poojari et al.(2008).3.1.4Inventory managementThe topic of robust multi-stage inventory management has been investigated in detail in Bienstock and Ozbay (2008)through the computation of robust basestock levels and Ben-Tal et al.(2009)through an extension of the Affinely Adjustable Robust Counterpart framework to control inventories under demand uncertainty.See and Sim (2010)studies a multi-period inventory control problem under ambiguous demand for which only mean,support and some measures of deviations are known,using a factor-based model.The parameters of the replenishment policies are obtained using a second-order conic programming problem.Song(2010)considers stochastic inventory control in robust supply chain systems.The work proposes an inte-grated approach that combines in a single step datafitting and inventory optimization–using histograms directly as the inputs for the optimization model–for the single-item multi-period periodic-review stochastic lot-sizing problem.Operation and planning issues for dynamic supply chain and transportation networks in uncertain envi-ronments are considered in Chung(2010),with examples drawn from emergency logistics planning,network design and congestion pricing problems.3.1.5Industry-specific applicationsAng et al.(2012)proposes a robust storage assignment approach in unit-load warehouses facing variable supply and uncertain demand in a multi-period setting.The authors assume a factor-based demand model and minimize the worst-case expected total travel in the warehouse with distributional ambiguity of demand.A related problem is considered in Werners and Wuelfing(2010),which optimizes internal transports at a parcel sorting center.Galli(2011)describes the models and algorithms that arise from implementing recoverable robust optimization to train platforming and rolling stock planning,where the concept of recoverable robustness has been defined in。

哈尔滨理工大学学报JOURNAL OF HARB! UNINERSINY OF SCINNCE AND TECHNOLOGY第26卷第、期2255年2月VoV 20 No. 1Feb. 2255SWISS 整流器多目标优化颜景斌，沈云森，刘思，魏金鑫，高崇禧(哈尔滨理工大学电气与电子工程学院，哈尔滨154082)摘 要：针对SWISS 整流器的性能问题，采用基于NSGA-P 算法的多目标优化方法。

以离散的直流电感、IGBT 、Dmde 以及输出电容参数建立的元器件数据库为约束条件，以效率、功率密度以 及输出纹波模型为目标函数，通过NSGA-H 算法进行优化，并给出了帕累托最优解集和帕累托最优 前沿，根据目标的优先级合理选择方案，从而选择相应器件。

最后，通过仿真实验表明方案的可行性,优化后效率为941 51%，功率密度为12. 96 kW/dm 5,输出纹波为5. 068。

关键词:SWISS 整流器；损耗；多目标优化；nsga -i i 算法DOS : 12.15633/4. jhusl. 2021.51.012中图分类号：TM46 文献标志码：A 文章编号：1057-2683(2521)51-0586-57Multi-objective Optimization of SWISS RectifierYAN Jing-bin , SHEN Yun-sen., LIU Si, WEI Jin-xin , GAO Chong-xi(School cf Elect/cal and Electronic Enyi-eeriny , Harbin Univeu/y cf Science and Technoloyy , Harbin 135085, China)Abstract : Aiminy xl tha peXounanca pndlem of SWISS recti —ci , - multi-oPjechvv optimization method bo —1on Non-Dominated Sotin- in Genetic Alyowthms-H ( NSGA-H - is aXopteb. With discrete DC —lductoi, IGBT, DOPa and output cax-citoi database -s constraints , and —FicOncy , powai dexsitp and output Uppla model -soPjechvv functions , tha optimization is co —deb out by NSGA-H alyorithm , usi — tha pareto optimal solution and pareto optimal front of tha alyorithm. Wa select tha dppnptma devica -ccorbin- to tha p/ottp of tha Um —.FOtly, tha simulation results show thul tha schema is feasible , tha optimized eWiciency is 96.61% , tha powai density O 12. 96 kW/4m 5 , and tha output Upple is 9. 665.Keywords ：SWISS nchfivi; loss; multi-oPjechvv optimization ; NSGA-H alyorithm2引言在整流器电力电子装置的研究中，希望构建一个综合性能最优的系统,即保证高效率的同时，又能使系统的体积、质量和成本等性能指标得到优化，这 是一个复杂的问题，往往以经验判断,可能无法保证其准确性，并且，各个性能之间一般相互冲突，如何对各系统进行多参数多目标优化并进行器件选型, 需使用合适的方法［一5］。

Draft:Deep Learning in Neural Networks:An OverviewTechnical Report IDSIA-03-14/arXiv:1404.7828(v1.5)[cs.NE]J¨u rgen SchmidhuberThe Swiss AI Lab IDSIAIstituto Dalle Molle di Studi sull’Intelligenza ArtificialeUniversity of Lugano&SUPSIGalleria2,6928Manno-LuganoSwitzerland15May2014AbstractIn recent years,deep artificial neural networks(including recurrent ones)have won numerous con-tests in pattern recognition and machine learning.This historical survey compactly summarises relevantwork,much of it from the previous millennium.Shallow and deep learners are distinguished by thedepth of their credit assignment paths,which are chains of possibly learnable,causal links between ac-tions and effects.I review deep supervised learning(also recapitulating the history of backpropagation),unsupervised learning,reinforcement learning&evolutionary computation,and indirect search for shortprograms encoding deep and large networks.PDF of earlier draft(v1):http://www.idsia.ch/∼juergen/DeepLearning30April2014.pdfLATEX source:http://www.idsia.ch/∼juergen/DeepLearning30April2014.texComplete BIBTEXfile:http://www.idsia.ch/∼juergen/bib.bibPrefaceThis is the draft of an invited Deep Learning(DL)overview.One of its goals is to assign credit to those who contributed to the present state of the art.I acknowledge the limitations of attempting to achieve this goal.The DL research community itself may be viewed as a continually evolving,deep network of scientists who have influenced each other in complex ways.Starting from recent DL results,I tried to trace back the origins of relevant ideas through the past half century and beyond,sometimes using“local search”to follow citations of citations backwards in time.Since not all DL publications properly acknowledge earlier relevant work,additional global search strategies were employed,aided by consulting numerous neural network experts.As a result,the present draft mostly consists of references(about800entries so far).Nevertheless,through an expert selection bias I may have missed important work.A related bias was surely introduced by my special familiarity with the work of my own DL research group in the past quarter-century.For these reasons,the present draft should be viewed as merely a snapshot of an ongoing credit assignment process.To help improve it,please do not hesitate to send corrections and suggestions to juergen@idsia.ch.Contents1Introduction to Deep Learning(DL)in Neural Networks(NNs)3 2Event-Oriented Notation for Activation Spreading in FNNs/RNNs3 3Depth of Credit Assignment Paths(CAPs)and of Problems4 4Recurring Themes of Deep Learning54.1Dynamic Programming(DP)for DL (5)4.2Unsupervised Learning(UL)Facilitating Supervised Learning(SL)and RL (6)4.3Occam’s Razor:Compression and Minimum Description Length(MDL) (6)4.4Learning Hierarchical Representations Through Deep SL,UL,RL (6)4.5Fast Graphics Processing Units(GPUs)for DL in NNs (6)5Supervised NNs,Some Helped by Unsupervised NNs75.11940s and Earlier (7)5.2Around1960:More Neurobiological Inspiration for DL (7)5.31965:Deep Networks Based on the Group Method of Data Handling(GMDH) (8)5.41979:Convolution+Weight Replication+Winner-Take-All(WTA) (8)5.51960-1981and Beyond:Development of Backpropagation(BP)for NNs (8)5.5.1BP for Weight-Sharing Feedforward NNs(FNNs)and Recurrent NNs(RNNs)..95.6Late1980s-2000:Numerous Improvements of NNs (9)5.6.1Ideas for Dealing with Long Time Lags and Deep CAPs (10)5.6.2Better BP Through Advanced Gradient Descent (10)5.6.3Discovering Low-Complexity,Problem-Solving NNs (11)5.6.4Potential Benefits of UL for SL (11)5.71987:UL Through Autoencoder(AE)Hierarchies (12)5.81989:BP for Convolutional NNs(CNNs) (13)5.91991:Fundamental Deep Learning Problem of Gradient Descent (13)5.101991:UL-Based History Compression Through a Deep Hierarchy of RNNs (14)5.111992:Max-Pooling(MP):Towards MPCNNs (14)5.121994:Contest-Winning Not So Deep NNs (15)5.131995:Supervised Recurrent Very Deep Learner(LSTM RNN) (15)5.142003:More Contest-Winning/Record-Setting,Often Not So Deep NNs (16)5.152006/7:Deep Belief Networks(DBNs)&AE Stacks Fine-Tuned by BP (17)5.162006/7:Improved CNNs/GPU-CNNs/BP-Trained MPCNNs (17)5.172009:First Official Competitions Won by RNNs,and with MPCNNs (18)5.182010:Plain Backprop(+Distortions)on GPU Yields Excellent Results (18)5.192011:MPCNNs on GPU Achieve Superhuman Vision Performance (18)5.202011:Hessian-Free Optimization for RNNs (19)5.212012:First Contests Won on ImageNet&Object Detection&Segmentation (19)5.222013-:More Contests and Benchmark Records (20)5.22.1Currently Successful Supervised Techniques:LSTM RNNs/GPU-MPCNNs (21)5.23Recent Tricks for Improving SL Deep NNs(Compare Sec.5.6.2,5.6.3) (21)5.24Consequences for Neuroscience (22)5.25DL with Spiking Neurons? (22)6DL in FNNs and RNNs for Reinforcement Learning(RL)236.1RL Through NN World Models Yields RNNs With Deep CAPs (23)6.2Deep FNNs for Traditional RL and Markov Decision Processes(MDPs) (24)6.3Deep RL RNNs for Partially Observable MDPs(POMDPs) (24)6.4RL Facilitated by Deep UL in FNNs and RNNs (25)6.5Deep Hierarchical RL(HRL)and Subgoal Learning with FNNs and RNNs (25)6.6Deep RL by Direct NN Search/Policy Gradients/Evolution (25)6.7Deep RL by Indirect Policy Search/Compressed NN Search (26)6.8Universal RL (27)7Conclusion271Introduction to Deep Learning(DL)in Neural Networks(NNs) Which modifiable components of a learning system are responsible for its success or failure?What changes to them improve performance?This has been called the fundamental credit assignment problem(Minsky, 1963).There are general credit assignment methods for universal problem solvers that are time-optimal in various theoretical senses(Sec.6.8).The present survey,however,will focus on the narrower,but now commercially important,subfield of Deep Learning(DL)in Artificial Neural Networks(NNs).We are interested in accurate credit assignment across possibly many,often nonlinear,computational stages of NNs.Shallow NN-like models have been around for many decades if not centuries(Sec.5.1).Models with several successive nonlinear layers of neurons date back at least to the1960s(Sec.5.3)and1970s(Sec.5.5). An efficient gradient descent method for teacher-based Supervised Learning(SL)in discrete,differentiable networks of arbitrary depth called backpropagation(BP)was developed in the1960s and1970s,and ap-plied to NNs in1981(Sec.5.5).BP-based training of deep NNs with many layers,however,had been found to be difficult in practice by the late1980s(Sec.5.6),and had become an explicit research subject by the early1990s(Sec.5.9).DL became practically feasible to some extent through the help of Unsupervised Learning(UL)(e.g.,Sec.5.10,5.15).The1990s and2000s also saw many improvements of purely super-vised DL(Sec.5).In the new millennium,deep NNs havefinally attracted wide-spread attention,mainly by outperforming alternative machine learning methods such as kernel machines(Vapnik,1995;Sch¨o lkopf et al.,1998)in numerous important applications.In fact,supervised deep NNs have won numerous of-ficial international pattern recognition competitions(e.g.,Sec.5.17,5.19,5.21,5.22),achieving thefirst superhuman visual pattern recognition results in limited domains(Sec.5.19).Deep NNs also have become relevant for the more generalfield of Reinforcement Learning(RL)where there is no supervising teacher (Sec.6).Both feedforward(acyclic)NNs(FNNs)and recurrent(cyclic)NNs(RNNs)have won contests(Sec.5.12,5.14,5.17,5.19,5.21,5.22).In a sense,RNNs are the deepest of all NNs(Sec.3)—they are general computers more powerful than FNNs,and can in principle create and process memories of ar-bitrary sequences of input patterns(e.g.,Siegelmann and Sontag,1991;Schmidhuber,1990a).Unlike traditional methods for automatic sequential program synthesis(e.g.,Waldinger and Lee,1969;Balzer, 1985;Soloway,1986;Deville and Lau,1994),RNNs can learn programs that mix sequential and parallel information processing in a natural and efficient way,exploiting the massive parallelism viewed as crucial for sustaining the rapid decline of computation cost observed over the past75years.The rest of this paper is structured as follows.Sec.2introduces a compact,event-oriented notation that is simple yet general enough to accommodate both FNNs and RNNs.Sec.3introduces the concept of Credit Assignment Paths(CAPs)to measure whether learning in a given NN application is of the deep or shallow type.Sec.4lists recurring themes of DL in SL,UL,and RL.Sec.5focuses on SL and UL,and on how UL can facilitate SL,although pure SL has become dominant in recent competitions(Sec.5.17-5.22). Sec.5is arranged in a historical timeline format with subsections on important inspirations and technical contributions.Sec.6on deep RL discusses traditional Dynamic Programming(DP)-based RL combined with gradient-based search techniques for SL or UL in deep NNs,as well as general methods for direct and indirect search in the weight space of deep FNNs and RNNs,including successful policy gradient and evolutionary methods.2Event-Oriented Notation for Activation Spreading in FNNs/RNNs Throughout this paper,let i,j,k,t,p,q,r denote positive integer variables assuming ranges implicit in the given contexts.Let n,m,T denote positive integer constants.An NN’s topology may change over time(e.g.,Fahlman,1991;Ring,1991;Weng et al.,1992;Fritzke, 1994).At any given moment,it can be described as afinite subset of units(or nodes or neurons)N= {u1,u2,...,}and afinite set H⊆N×N of directed edges or connections between nodes.FNNs are acyclic graphs,RNNs cyclic.Thefirst(input)layer is the set of input units,a subset of N.In FNNs,the k-th layer(k>1)is the set of all nodes u∈N such that there is an edge path of length k−1(but no longer path)between some input unit and u.There may be shortcut connections between distant layers.The NN’s behavior or program is determined by a set of real-valued,possibly modifiable,parameters or weights w i(i=1,...,n).We now focus on a singlefinite episode or epoch of information processing and activation spreading,without learning through weight changes.The following slightly unconventional notation is designed to compactly describe what is happening during the runtime of the system.During an episode,there is a partially causal sequence x t(t=1,...,T)of real values that I call events.Each x t is either an input set by the environment,or the activation of a unit that may directly depend on other x k(k<t)through a current NN topology-dependent set in t of indices k representing incoming causal connections or links.Let the function v encode topology information and map such event index pairs(k,t)to weight indices.For example,in the non-input case we may have x t=f t(net t)with real-valued net t= k∈in t x k w v(k,t)(additive case)or net t= k∈in t x k w v(k,t)(multiplicative case), where f t is a typically nonlinear real-valued activation function such as tanh.In many recent competition-winning NNs(Sec.5.19,5.21,5.22)there also are events of the type x t=max k∈int (x k);some networktypes may also use complex polynomial activation functions(Sec.5.3).x t may directly affect certain x k(k>t)through outgoing connections or links represented through a current set out t of indices k with t∈in k.Some non-input events are called output events.Note that many of the x t may refer to different,time-varying activations of the same unit in sequence-processing RNNs(e.g.,Williams,1989,“unfolding in time”),or also in FNNs sequentially exposed to time-varying input patterns of a large training set encoded as input events.During an episode,the same weight may get reused over and over again in topology-dependent ways,e.g.,in RNNs,or in convolutional NNs(Sec.5.4,5.8).I call this weight sharing across space and/or time.Weight sharing may greatly reduce the NN’s descriptive complexity,which is the number of bits of information required to describe the NN (Sec.4.3).In Supervised Learning(SL),certain NN output events x t may be associated with teacher-given,real-valued labels or targets d t yielding errors e t,e.g.,e t=1/2(x t−d t)2.A typical goal of supervised NN training is tofind weights that yield episodes with small total error E,the sum of all such e t.The hope is that the NN will generalize well in later episodes,causing only small errors on previously unseen sequences of input events.Many alternative error functions for SL and UL are possible.SL assumes that input events are independent of earlier output events(which may affect the environ-ment through actions causing subsequent perceptions).This assumption does not hold in the broaderfields of Sequential Decision Making and Reinforcement Learning(RL)(Kaelbling et al.,1996;Sutton and Barto, 1998;Hutter,2005)(Sec.6).In RL,some of the input events may encode real-valued reward signals given by the environment,and a typical goal is tofind weights that yield episodes with a high sum of reward signals,through sequences of appropriate output actions.Sec.5.5will use the notation above to compactly describe a central algorithm of DL,namely,back-propagation(BP)for supervised weight-sharing FNNs and RNNs.(FNNs may be viewed as RNNs with certainfixed zero weights.)Sec.6will address the more general RL case.3Depth of Credit Assignment Paths(CAPs)and of ProblemsTo measure whether credit assignment in a given NN application is of the deep or shallow type,I introduce the concept of Credit Assignment Paths or CAPs,which are chains of possibly causal links between events.Let usfirst focus on SL.Consider two events x p and x q(1≤p<q≤T).Depending on the appli-cation,they may have a Potential Direct Causal Connection(PDCC)expressed by the Boolean predicate pdcc(p,q),which is true if and only if p∈in q.Then the2-element list(p,q)is defined to be a CAP from p to q(a minimal one).A learning algorithm may be allowed to change w v(p,q)to improve performance in future episodes.More general,possibly indirect,Potential Causal Connections(PCC)are expressed by the recursively defined Boolean predicate pcc(p,q),which in the SL case is true only if pdcc(p,q),or if pcc(p,k)for some k and pdcc(k,q).In the latter case,appending q to any CAP from p to k yields a CAP from p to q(this is a recursive definition,too).The set of such CAPs may be large but isfinite.Note that the same weight may affect many different PDCCs between successive events listed by a given CAP,e.g.,in the case of RNNs, or weight-sharing FNNs.Suppose a CAP has the form(...,k,t,...,q),where k and t(possibly t=q)are thefirst successive elements with modifiable w v(k,t).Then the length of the suffix list(t,...,q)is called the CAP’s depth (which is0if there are no modifiable links at all).This depth limits how far backwards credit assignment can move down the causal chain tofind a modifiable weight.1Suppose an episode and its event sequence x1,...,x T satisfy a computable criterion used to decide whether a given problem has been solved(e.g.,total error E below some threshold).Then the set of used weights is called a solution to the problem,and the depth of the deepest CAP within the sequence is called the solution’s depth.There may be other solutions(yielding different event sequences)with different depths.Given somefixed NN topology,the smallest depth of any solution is called the problem’s depth.Sometimes we also speak of the depth of an architecture:SL FNNs withfixed topology imply a problem-independent maximal problem depth bounded by the number of non-input layers.Certain SL RNNs withfixed weights for all connections except those to output units(Jaeger,2001;Maass et al.,2002; Jaeger,2004;Schrauwen et al.,2007)have a maximal problem depth of1,because only thefinal links in the corresponding CAPs are modifiable.In general,however,RNNs may learn to solve problems of potentially unlimited depth.Note that the definitions above are solely based on the depths of causal chains,and agnostic of the temporal distance between events.For example,shallow FNNs perceiving large“time windows”of in-put events may correctly classify long input sequences through appropriate output events,and thus solve shallow problems involving long time lags between relevant events.At which problem depth does Shallow Learning end,and Deep Learning begin?Discussions with DL experts have not yet yielded a conclusive response to this question.Instead of committing myself to a precise answer,let me just define for the purposes of this overview:problems of depth>10require Very Deep Learning.The difficulty of a problem may have little to do with its depth.Some NNs can quickly learn to solve certain deep problems,e.g.,through random weight guessing(Sec.5.9)or other types of direct search (Sec.6.6)or indirect search(Sec.6.7)in weight space,or through training an NNfirst on shallow problems whose solutions may then generalize to deep problems,or through collapsing sequences of(non)linear operations into a single(non)linear operation—but see an analysis of non-trivial aspects of deep linear networks(Baldi and Hornik,1994,Section B).In general,however,finding an NN that precisely models a given training set is an NP-complete problem(Judd,1990;Blum and Rivest,1992),also in the case of deep NNs(S´ıma,1994;de Souto et al.,1999;Windisch,2005);compare a survey of negative results(S´ıma, 2002,Section1).Above we have focused on SL.In the more general case of RL in unknown environments,pcc(p,q) is also true if x p is an output event and x q any later input event—any action may affect the environment and thus any later perception.(In the real world,the environment may even influence non-input events computed on a physical hardware entangled with the entire universe,but this is ignored here.)It is possible to model and replace such unmodifiable environmental PCCs through a part of the NN that has already learned to predict(through some of its units)input events(including reward signals)from former input events and actions(Sec.6.1).Its weights are frozen,but can help to assign credit to other,still modifiable weights used to compute actions(Sec.6.1).This approach may lead to very deep CAPs though.Some DL research is about automatically rephrasing problems such that their depth is reduced(Sec.4). In particular,sometimes UL is used to make SL problems less deep,e.g.,Sec.5.10.Often Dynamic Programming(Sec.4.1)is used to facilitate certain traditional RL problems,e.g.,Sec.6.2.Sec.5focuses on CAPs for SL,Sec.6on the more complex case of RL.4Recurring Themes of Deep Learning4.1Dynamic Programming(DP)for DLOne recurring theme of DL is Dynamic Programming(DP)(Bellman,1957),which can help to facili-tate credit assignment under certain assumptions.For example,in SL NNs,backpropagation itself can 1An alternative would be to count only modifiable links when measuring depth.In many typical NN applications this would not make a difference,but in some it would,e.g.,Sec.6.1.be viewed as a DP-derived method(Sec.5.5).In traditional RL based on strong Markovian assumptions, DP-derived methods can help to greatly reduce problem depth(Sec.6.2).DP algorithms are also essen-tial for systems that combine concepts of NNs and graphical models,such as Hidden Markov Models (HMMs)(Stratonovich,1960;Baum and Petrie,1966)and Expectation Maximization(EM)(Dempster et al.,1977),e.g.,(Bottou,1991;Bengio,1991;Bourlard and Morgan,1994;Baldi and Chauvin,1996; Jordan and Sejnowski,2001;Bishop,2006;Poon and Domingos,2011;Dahl et al.,2012;Hinton et al., 2012a).4.2Unsupervised Learning(UL)Facilitating Supervised Learning(SL)and RL Another recurring theme is how UL can facilitate both SL(Sec.5)and RL(Sec.6).UL(Sec.5.6.4) is normally used to encode raw incoming data such as video or speech streams in a form that is more convenient for subsequent goal-directed learning.In particular,codes that describe the original data in a less redundant or more compact way can be fed into SL(Sec.5.10,5.15)or RL machines(Sec.6.4),whose search spaces may thus become smaller(and whose CAPs shallower)than those necessary for dealing with the raw data.UL is closely connected to the topics of regularization and compression(Sec.4.3,5.6.3). 4.3Occam’s Razor:Compression and Minimum Description Length(MDL) Occam’s razor favors simple solutions over complex ones.Given some programming language,the prin-ciple of Minimum Description Length(MDL)can be used to measure the complexity of a solution candi-date by the length of the shortest program that computes it(e.g.,Solomonoff,1964;Kolmogorov,1965b; Chaitin,1966;Wallace and Boulton,1968;Levin,1973a;Rissanen,1986;Blumer et al.,1987;Li and Vit´a nyi,1997;Gr¨u nwald et al.,2005).Some methods explicitly take into account program runtime(Al-lender,1992;Watanabe,1992;Schmidhuber,2002,1995);many consider only programs with constant runtime,written in non-universal programming languages(e.g.,Rissanen,1986;Hinton and van Camp, 1993).In the NN case,the MDL principle suggests that low NN weight complexity corresponds to high NN probability in the Bayesian view(e.g.,MacKay,1992;Buntine and Weigend,1991;De Freitas,2003), and to high generalization performance(e.g.,Baum and Haussler,1989),without overfitting the training data.Many methods have been proposed for regularizing NNs,that is,searching for solution-computing, low-complexity SL NNs(Sec.5.6.3)and RL NNs(Sec.6.7).This is closely related to certain UL methods (Sec.4.2,5.6.4).4.4Learning Hierarchical Representations Through Deep SL,UL,RLMany methods of Good Old-Fashioned Artificial Intelligence(GOFAI)(Nilsson,1980)as well as more recent approaches to AI(Russell et al.,1995)and Machine Learning(Mitchell,1997)learn hierarchies of more and more abstract data representations.For example,certain methods of syntactic pattern recog-nition(Fu,1977)such as grammar induction discover hierarchies of formal rules to model observations. The partially(un)supervised Automated Mathematician/EURISKO(Lenat,1983;Lenat and Brown,1984) continually learns concepts by combining previously learnt concepts.Such hierarchical representation learning(Ring,1994;Bengio et al.,2013;Deng and Yu,2014)is also a recurring theme of DL NNs for SL (Sec.5),UL-aided SL(Sec.5.7,5.10,5.15),and hierarchical RL(Sec.6.5).Often,abstract hierarchical representations are natural by-products of data compression(Sec.4.3),e.g.,Sec.5.10.4.5Fast Graphics Processing Units(GPUs)for DL in NNsWhile the previous millennium saw several attempts at creating fast NN-specific hardware(e.g.,Jackel et al.,1990;Faggin,1992;Ramacher et al.,1993;Widrow et al.,1994;Heemskerk,1995;Korkin et al., 1997;Urlbe,1999),and at exploiting standard hardware(e.g.,Anguita et al.,1994;Muller et al.,1995; Anguita and Gomes,1996),the new millennium brought a DL breakthrough in form of cheap,multi-processor graphics cards or GPUs.GPUs are widely used for video games,a huge and competitive market that has driven down hardware prices.GPUs excel at fast matrix and vector multiplications required not only for convincing virtual realities but also for NN training,where they can speed up learning by a factorof50and more.Some of the GPU-based FNN implementations(Sec.5.16-5.19)have greatly contributed to recent successes in contests for pattern recognition(Sec.5.19-5.22),image segmentation(Sec.5.21), and object detection(Sec.5.21-5.22).5Supervised NNs,Some Helped by Unsupervised NNsThe main focus of current practical applications is on Supervised Learning(SL),which has dominated re-cent pattern recognition contests(Sec.5.17-5.22).Several methods,however,use additional Unsupervised Learning(UL)to facilitate SL(Sec.5.7,5.10,5.15).It does make sense to treat SL and UL in the same section:often gradient-based methods,such as BP(Sec.5.5.1),are used to optimize objective functions of both UL and SL,and the boundary between SL and UL may blur,for example,when it comes to time series prediction and sequence classification,e.g.,Sec.5.10,5.12.A historical timeline format will help to arrange subsections on important inspirations and techni-cal contributions(although such a subsection may span a time interval of many years).Sec.5.1briefly mentions early,shallow NN models since the1940s,Sec.5.2additional early neurobiological inspiration relevant for modern Deep Learning(DL).Sec.5.3is about GMDH networks(since1965),perhaps thefirst (feedforward)DL systems.Sec.5.4is about the relatively deep Neocognitron NN(1979)which is similar to certain modern deep FNN architectures,as it combines convolutional NNs(CNNs),weight pattern repli-cation,and winner-take-all(WTA)mechanisms.Sec.5.5uses the notation of Sec.2to compactly describe a central algorithm of DL,namely,backpropagation(BP)for supervised weight-sharing FNNs and RNNs. It also summarizes the history of BP1960-1981and beyond.Sec.5.6describes problems encountered in the late1980s with BP for deep NNs,and mentions several ideas from the previous millennium to overcome them.Sec.5.7discusses afirst hierarchical stack of coupled UL-based Autoencoders(AEs)—this concept resurfaced in the new millennium(Sec.5.15).Sec.5.8is about applying BP to CNNs,which is important for today’s DL applications.Sec.5.9explains BP’s Fundamental DL Problem(of vanishing/exploding gradients)discovered in1991.Sec.5.10explains how a deep RNN stack of1991(the History Compressor) pre-trained by UL helped to solve previously unlearnable DL benchmarks requiring Credit Assignment Paths(CAPs,Sec.3)of depth1000and more.Sec.5.11discusses a particular WTA method called Max-Pooling(MP)important in today’s DL FNNs.Sec.5.12mentions afirst important contest won by SL NNs in1994.Sec.5.13describes a purely supervised DL RNN(Long Short-Term Memory,LSTM)for problems of depth1000and more.Sec.5.14mentions an early contest of2003won by an ensemble of shallow NNs, as well as good pattern recognition results with CNNs and LSTM RNNs(2003).Sec.5.15is mostly about Deep Belief Networks(DBNs,2006)and related stacks of Autoencoders(AEs,Sec.5.7)pre-trained by UL to facilitate BP-based SL.Sec.5.16mentions thefirst BP-trained MPCNNs(2007)and GPU-CNNs(2006). Sec.5.17-5.22focus on official competitions with secret test sets won by(mostly purely supervised)DL NNs since2009,in sequence recognition,image classification,image segmentation,and object detection. Many RNN results depended on LSTM(Sec.5.13);many FNN results depended on GPU-based FNN code developed since2004(Sec.5.16,5.17,5.18,5.19),in particular,GPU-MPCNNs(Sec.5.19).5.11940s and EarlierNN research started in the1940s(e.g.,McCulloch and Pitts,1943;Hebb,1949);compare also later work on learning NNs(Rosenblatt,1958,1962;Widrow and Hoff,1962;Grossberg,1969;Kohonen,1972; von der Malsburg,1973;Narendra and Thathatchar,1974;Willshaw and von der Malsburg,1976;Palm, 1980;Hopfield,1982).In a sense NNs have been around even longer,since early supervised NNs were essentially variants of linear regression methods going back at least to the early1800s(e.g.,Legendre, 1805;Gauss,1809,1821).Early NNs had a maximal CAP depth of1(Sec.3).5.2Around1960:More Neurobiological Inspiration for DLSimple cells and complex cells were found in the cat’s visual cortex(e.g.,Hubel and Wiesel,1962;Wiesel and Hubel,1959).These cellsfire in response to certain properties of visual sensory inputs,such as theorientation of plex cells exhibit more spatial invariance than simple cells.This inspired later deep NN architectures(Sec.5.4)used in certain modern award-winning Deep Learners(Sec.5.19-5.22).5.31965:Deep Networks Based on the Group Method of Data Handling(GMDH) Networks trained by the Group Method of Data Handling(GMDH)(Ivakhnenko and Lapa,1965; Ivakhnenko et al.,1967;Ivakhnenko,1968,1971)were perhaps thefirst DL systems of the Feedforward Multilayer Perceptron type.The units of GMDH nets may have polynomial activation functions imple-menting Kolmogorov-Gabor polynomials(more general than traditional NN activation functions).Given a training set,layers are incrementally grown and trained by regression analysis,then pruned with the help of a separate validation set(using today’s terminology),where Decision Regularisation is used to weed out superfluous units.The numbers of layers and units per layer can be learned in problem-dependent fashion. This is a good example of hierarchical representation learning(Sec.4.4).There have been numerous ap-plications of GMDH-style networks,e.g.(Ikeda et al.,1976;Farlow,1984;Madala and Ivakhnenko,1994; Ivakhnenko,1995;Kondo,1998;Kord´ık et al.,2003;Witczak et al.,2006;Kondo and Ueno,2008).5.41979:Convolution+Weight Replication+Winner-Take-All(WTA)Apart from deep GMDH networks(Sec.5.3),the Neocognitron(Fukushima,1979,1980,2013a)was per-haps thefirst artificial NN that deserved the attribute deep,and thefirst to incorporate the neurophysiolog-ical insights of Sec.5.2.It introduced convolutional NNs(today often called CNNs or convnets),where the(typically rectangular)receptivefield of a convolutional unit with given weight vector is shifted step by step across a2-dimensional array of input values,such as the pixels of an image.The resulting2D array of subsequent activation events of this unit can then provide inputs to higher-level units,and so on.Due to massive weight replication(Sec.2),relatively few parameters may be necessary to describe the behavior of such a convolutional layer.Competition layers have WTA subsets whose maximally active units are the only ones to adopt non-zero activation values.They essentially“down-sample”the competition layer’s input.This helps to create units whose responses are insensitive to small image shifts(compare Sec.5.2).The Neocognitron is very similar to the architecture of modern,contest-winning,purely super-vised,feedforward,gradient-based Deep Learners with alternating convolutional and competition lay-ers(e.g.,Sec.5.19-5.22).Fukushima,however,did not set the weights by supervised backpropagation (Sec.5.5,5.8),but by local un supervised learning rules(e.g.,Fukushima,2013b),or by pre-wiring.In that sense he did not care for the DL problem(Sec.5.9),although his architecture was comparatively deep indeed.He also used Spatial Averaging(Fukushima,1980,2011)instead of Max-Pooling(MP,Sec.5.11), currently a particularly convenient and popular WTA mechanism.Today’s CNN-based DL machines profita lot from later CNN work(e.g.,LeCun et al.,1989;Ranzato et al.,2007)(Sec.5.8,5.16,5.19).5.51960-1981and Beyond:Development of Backpropagation(BP)for NNsThe minimisation of errors through gradient descent(Hadamard,1908)in the parameter space of com-plex,nonlinear,differentiable,multi-stage,NN-related systems has been discussed at least since the early 1960s(e.g.,Kelley,1960;Bryson,1961;Bryson and Denham,1961;Pontryagin et al.,1961;Dreyfus,1962; Wilkinson,1965;Amari,1967;Bryson and Ho,1969;Director and Rohrer,1969;Griewank,2012),ini-tially within the framework of Euler-LaGrange equations in the Calculus of Variations(e.g.,Euler,1744). Steepest descent in such systems can be performed(Bryson,1961;Kelley,1960;Bryson and Ho,1969)by iterating the ancient chain rule(Leibniz,1676;L’Hˆo pital,1696)in Dynamic Programming(DP)style(Bell-man,1957).A simplified derivation of the method uses the chain rule only(Dreyfus,1962).The methods of the1960s were already efficient in the DP sense.However,they backpropagated derivative information through standard Jacobian matrix calculations from one“layer”to the previous one, explicitly addressing neither direct links across several layers nor potential additional efficiency gains due to network sparsity(but perhaps such enhancements seemed obvious to the authors).。

425 BibliographyH.A KAIKE(1974).Markovian representation of stochastic processes and its application to the analysis of autoregressive moving average processes.Annals Institute Statistical Mathematics,vol.26,pp.363-387. B.D.O.A NDERSON and J.B.M OORE(1979).Optimal rmation and System Sciences Series, Prentice Hall,Englewood Cliffs,NJ.T.W.A NDERSON(1971).The Statistical Analysis of Time Series.Series in Probability and Mathematical Statistics,Wiley,New York.R.A NDRE-O BRECHT(1988).A new statistical approach for the automatic segmentation of continuous speech signals.IEEE Trans.Acoustics,Speech,Signal Processing,vol.ASSP-36,no1,pp.29-40.R.A NDRE-O BRECHT(1990).Reconnaissance automatique de parole`a partir de segments acoustiques et de mod`e les de Markov cach´e s.Proc.Journ´e es Etude de la Parole,Montr´e al,May1990(in French).R.A NDRE-O BRECHT and H.Y.S U(1988).Three acoustic labellings for phoneme based continuous speech recognition.Proc.Speech’88,Edinburgh,UK,pp.943-950.U.A PPEL and A.VON B RANDT(1983).Adaptive sequential segmentation of piecewise stationary time rmation Sciences,vol.29,no1,pp.27-56.L.A.A ROIAN and H.L EVENE(1950).The effectiveness of quality control procedures.Jal American Statis-tical Association,vol.45,pp.520-529.K.J.A STR¨OM and B.W ITTENMARK(1984).Computer Controlled Systems:Theory and rma-tion and System Sciences Series,Prentice Hall,Englewood Cliffs,NJ.M.B AGSHAW and R.A.J OHNSON(1975a).The effect of serial correlation on the performance of CUSUM tests-Part II.Technometrics,vol.17,no1,pp.73-80.M.B AGSHAW and R.A.J OHNSON(1975b).The influence of reference values and estimated variance on the ARL of CUSUM tests.Jal Royal Statistical Society,vol.37(B),no3,pp.413-420.M.B AGSHAW and R.A.J OHNSON(1977).Sequential procedures for detecting parameter changes in a time-series model.Jal American Statistical Association,vol.72,no359,pp.593-597.R.K.B ANSAL and P.P APANTONI-K AZAKOS(1986).An algorithm for detecting a change in a stochastic process.IEEE rmation Theory,vol.IT-32,no2,pp.227-235.G.A.B ARNARD(1959).Control charts and stochastic processes.Jal Royal Statistical Society,vol.B.21, pp.239-271.A.E.B ASHARINOV andB.S.F LEISHMAN(1962).Methods of the statistical sequential analysis and their radiotechnical applications.Sovetskoe Radio,Moscow(in Russian).M.B ASSEVILLE(1978).D´e viations par rapport au maximum:formules d’arrˆe t et martingales associ´e es. Compte-rendus du S´e minaire de Probabilit´e s,Universit´e de Rennes I.M.B ASSEVILLE(1981).Edge detection using sequential methods for change in level-Part II:Sequential detection of change in mean.IEEE Trans.Acoustics,Speech,Signal Processing,vol.ASSP-29,no1,pp.32-50.426B IBLIOGRAPHY M.B ASSEVILLE(1982).A survey of statistical failure detection techniques.In Contribution`a la D´e tectionS´e quentielle de Ruptures de Mod`e les Statistiques,Th`e se d’Etat,Universit´e de Rennes I,France(in English). M.B ASSEVILLE(1986).The two-models approach for the on-line detection of changes in AR processes. In Detection of Abrupt Changes in Signals and Dynamical Systems(M.Basseville,A.Benveniste,eds.). Lecture Notes in Control and Information Sciences,LNCIS77,Springer,New York,pp.169-215.M.B ASSEVILLE(1988).Detecting changes in signals and systems-A survey.Automatica,vol.24,pp.309-326.M.B ASSEVILLE(1989).Distance measures for signal processing and pattern recognition.Signal Process-ing,vol.18,pp.349-369.M.B ASSEVILLE and A.B ENVENISTE(1983a).Design and comparative study of some sequential jump detection algorithms for digital signals.IEEE Trans.Acoustics,Speech,Signal Processing,vol.ASSP-31, no3,pp.521-535.M.B ASSEVILLE and A.B ENVENISTE(1983b).Sequential detection of abrupt changes in spectral charac-teristics of digital signals.IEEE rmation Theory,vol.IT-29,no5,pp.709-724.M.B ASSEVILLE and A.B ENVENISTE,eds.(1986).Detection of Abrupt Changes in Signals and Dynamical Systems.Lecture Notes in Control and Information Sciences,LNCIS77,Springer,New York.M.B ASSEVILLE and I.N IKIFOROV(1991).A unified framework for statistical change detection.Proc.30th IEEE Conference on Decision and Control,Brighton,UK.M.B ASSEVILLE,B.E SPIAU and J.G ASNIER(1981).Edge detection using sequential methods for change in level-Part I:A sequential edge detection algorithm.IEEE Trans.Acoustics,Speech,Signal Processing, vol.ASSP-29,no1,pp.24-31.M.B ASSEVILLE, A.B ENVENISTE and G.M OUSTAKIDES(1986).Detection and diagnosis of abrupt changes in modal characteristics of nonstationary digital signals.IEEE rmation Theory,vol.IT-32,no3,pp.412-417.M.B ASSEVILLE,A.B ENVENISTE,G.M OUSTAKIDES and A.R OUG´E E(1987a).Detection and diagnosis of changes in the eigenstructure of nonstationary multivariable systems.Automatica,vol.23,no3,pp.479-489. M.B ASSEVILLE,A.B ENVENISTE,G.M OUSTAKIDES and A.R OUG´E E(1987b).Optimal sensor location for detecting changes in dynamical behavior.IEEE Trans.Automatic Control,vol.AC-32,no12,pp.1067-1075.M.B ASSEVILLE,A.B ENVENISTE,B.G ACH-D EVAUCHELLE,M.G OURSAT,D.B ONNECASE,P.D OREY, M.P REVOSTO and M.O LAGNON(1993).Damage monitoring in vibration mechanics:issues in diagnos-tics and predictive maintenance.Mechanical Systems and Signal Processing,vol.7,no5,pp.401-423.R.V.B EARD(1971).Failure Accommodation in Linear Systems through Self-reorganization.Ph.D.Thesis, Dept.Aeronautics and Astronautics,MIT,Cambridge,MA.A.B ENVENISTE and J.J.F UCHS(1985).Single sample modal identification of a nonstationary stochastic process.IEEE Trans.Automatic Control,vol.AC-30,no1,pp.66-74.A.B ENVENISTE,M.B ASSEVILLE and G.M OUSTAKIDES(1987).The asymptotic local approach to change detection and model validation.IEEE Trans.Automatic Control,vol.AC-32,no7,pp.583-592.A.B ENVENISTE,M.M ETIVIER and P.P RIOURET(1990).Adaptive Algorithms and Stochastic Approxima-tions.Series on Applications of Mathematics,(A.V.Balakrishnan,I.Karatzas,M.Yor,eds.).Springer,New York.A.B ENVENISTE,M.B ASSEVILLE,L.E L G HAOUI,R.N IKOUKHAH and A.S.W ILLSKY(1992).An optimum robust approach to statistical failure detection and identification.IFAC World Conference,Sydney, July1993.B IBLIOGRAPHY427 R.H.B ERK(1973).Some asymptotic aspects of sequential analysis.Annals Statistics,vol.1,no6,pp.1126-1138.R.H.B ERK(1975).Locally most powerful sequential test.Annals Statistics,vol.3,no2,pp.373-381.P.B ILLINGSLEY(1968).Convergence of Probability Measures.Wiley,New York.A.F.B ISSELL(1969).Cusum techniques for quality control.Applied Statistics,vol.18,pp.1-30.M.E.B IVAIKOV(1991).Control of the sample size for recursive estimation of parameters subject to abrupt changes.Automation and Remote Control,no9,pp.96-103.R.E.B LAHUT(1987).Principles and Practice of Information Theory.Addison-Wesley,Reading,MA.I.F.B LAKE and W.C.L INDSEY(1973).Level-crossing problems for random processes.IEEE r-mation Theory,vol.IT-19,no3,pp.295-315.G.B ODENSTEIN and H.M.P RAETORIUS(1977).Feature extraction from the encephalogram by adaptive segmentation.Proc.IEEE,vol.65,pp.642-652.T.B OHLIN(1977).Analysis of EEG signals with changing spectra using a short word Kalman estimator. Mathematical Biosciences,vol.35,pp.221-259.W.B¨OHM and P.H ACKL(1990).Improved bounds for the average run length of control charts based on finite weighted sums.Annals Statistics,vol.18,no4,pp.1895-1899.T.B OJDECKI and J.H OSZA(1984).On a generalized disorder problem.Stochastic Processes and their Applications,vol.18,pp.349-359.L.I.B ORODKIN and V.V.M OTTL’(1976).Algorithm forfinding the jump times of random process equation parameters.Automation and Remote Control,vol.37,no6,Part1,pp.23-32.A.A.B OROVKOV(1984).Theory of Mathematical Statistics-Estimation and Hypotheses Testing,Naouka, Moscow(in Russian).Translated in French under the title Statistique Math´e matique-Estimation et Tests d’Hypoth`e ses,Mir,Paris,1987.G.E.P.B OX and G.M.J ENKINS(1970).Time Series Analysis,Forecasting and Control.Series in Time Series Analysis,Holden-Day,San Francisco.A.VON B RANDT(1983).Detecting and estimating parameters jumps using ladder algorithms and likelihood ratio test.Proc.ICASSP,Boston,MA,pp.1017-1020.A.VON B RANDT(1984).Modellierung von Signalen mit Sprunghaft Ver¨a nderlichem Leistungsspektrum durch Adaptive Segmentierung.Doctor-Engineer Dissertation,M¨u nchen,RFA(in German).S.B RAUN,ed.(1986).Mechanical Signature Analysis-Theory and Applications.Academic Press,London. L.B REIMAN(1968).Probability.Series in Statistics,Addison-Wesley,Reading,MA.G.S.B RITOV and L.A.M IRONOVSKI(1972).Diagnostics of linear systems of automatic regulation.Tekh. Kibernetics,vol.1,pp.76-83.B.E.B RODSKIY and B.S.D ARKHOVSKIY(1992).Nonparametric Methods in Change-point Problems. Kluwer Academic,Boston.L.D.B ROEMELING(1982).Jal Econometrics,vol.19,Special issue on structural change in Econometrics. L.D.B ROEMELING and H.T SURUMI(1987).Econometrics and Structural Change.Dekker,New York. D.B ROOK and D.A.E VANS(1972).An approach to the probability distribution of Cusum run length. Biometrika,vol.59,pp.539-550.J.B RUNET,D.J AUME,M.L ABARR`E RE,A.R AULT and M.V ERG´E(1990).D´e tection et Diagnostic de Pannes.Trait´e des Nouvelles Technologies,S´e rie Diagnostic et Maintenance,Herm`e s,Paris(in French).428B IBLIOGRAPHY S.P.B RUZZONE and M.K AVEH(1984).Information tradeoffs in using the sample autocorrelation function in ARMA parameter estimation.IEEE Trans.Acoustics,Speech,Signal Processing,vol.ASSP-32,no4, pp.701-715.A.K.C AGLAYAN(1980).Necessary and sufficient conditions for detectability of jumps in linear systems. IEEE Trans.Automatic Control,vol.AC-25,no4,pp.833-834.A.K.C AGLAYAN and R.E.L ANCRAFT(1983).Reinitialization issues in fault tolerant systems.Proc.Amer-ican Control Conf.,pp.952-955.A.K.C AGLAYAN,S.M.A LLEN and K.W EHMULLER(1988).Evaluation of a second generation reconfigu-ration strategy for aircraftflight control systems subjected to actuator failure/surface damage.Proc.National Aerospace and Electronic Conference,Dayton,OH.P.E.C AINES(1988).Linear Stochastic Systems.Series in Probability and Mathematical Statistics,Wiley, New York.M.J.C HEN and J.P.N ORTON(1987).Estimation techniques for tracking rapid parameter changes.Intern. Jal Control,vol.45,no4,pp.1387-1398.W.K.C HIU(1974).The economic design of cusum charts for controlling normal mean.Applied Statistics, vol.23,no3,pp.420-433.E.Y.C HOW(1980).A Failure Detection System Design Methodology.Ph.D.Thesis,M.I.T.,L.I.D.S.,Cam-bridge,MA.E.Y.C HOW and A.S.W ILLSKY(1984).Analytical redundancy and the design of robust failure detection systems.IEEE Trans.Automatic Control,vol.AC-29,no3,pp.689-691.Y.S.C HOW,H.R OBBINS and D.S IEGMUND(1971).Great Expectations:The Theory of Optimal Stop-ping.Houghton-Mifflin,Boston.R.N.C LARK,D.C.F OSTH and V.M.W ALTON(1975).Detection of instrument malfunctions in control systems.IEEE Trans.Aerospace Electronic Systems,vol.AES-11,pp.465-473.A.C OHEN(1987).Biomedical Signal Processing-vol.1:Time and Frequency Domain Analysis;vol.2: Compression and Automatic Recognition.CRC Press,Boca Raton,FL.J.C ORGE and F.P UECH(1986).Analyse du rythme cardiaque foetal par des m´e thodes de d´e tection de ruptures.Proc.7th INRIA Int.Conf.Analysis and optimization of Systems.Antibes,FR(in French).D.R.C OX and D.V.H INKLEY(1986).Theoretical Statistics.Chapman and Hall,New York.D.R.C OX and H.D.M ILLER(1965).The Theory of Stochastic Processes.Wiley,New York.S.V.C ROWDER(1987).A simple method for studying run-length distributions of exponentially weighted moving average charts.Technometrics,vol.29,no4,pp.401-407.H.C S¨ORG¨O and L.H ORV´ATH(1988).Nonparametric methods for change point problems.In Handbook of Statistics(P.R.Krishnaiah,C.R.Rao,eds.),vol.7,Elsevier,New York,pp.403-425.R.B.D AVIES(1973).Asymptotic inference in stationary gaussian time series.Advances Applied Probability, vol.5,no3,pp.469-497.J.C.D ECKERT,M.N.D ESAI,J.J.D EYST and A.S.W ILLSKY(1977).F-8DFBW sensor failure identification using analytical redundancy.IEEE Trans.Automatic Control,vol.AC-22,no5,pp.795-803.M.H.D E G ROOT(1970).Optimal Statistical Decisions.Series in Probability and Statistics,McGraw-Hill, New York.J.D ESHAYES and D.P ICARD(1979).Tests de ruptures dans un mod`e pte-Rendus de l’Acad´e mie des Sciences,vol.288,Ser.A,pp.563-566(in French).B IBLIOGRAPHY429 J.D ESHAYES and D.P ICARD(1983).Ruptures de Mod`e les en Statistique.Th`e ses d’Etat,Universit´e deParis-Sud,Orsay,France(in French).J.D ESHAYES and D.P ICARD(1986).Off-line statistical analysis of change-point models using non para-metric and likelihood methods.In Detection of Abrupt Changes in Signals and Dynamical Systems(M. Basseville,A.Benveniste,eds.).Lecture Notes in Control and Information Sciences,LNCIS77,Springer, New York,pp.103-168.B.D EVAUCHELLE-G ACH(1991).Diagnostic M´e canique des Fatigues sur les Structures Soumises`a des Vibrations en Ambiance de Travail.Th`e se de l’Universit´e Paris IX Dauphine(in French).B.D EVAUCHELLE-G ACH,M.B ASSEVILLE and A.B ENVENISTE(1991).Diagnosing mechanical changes in vibrating systems.Proc.SAFEPROCESS’91,Baden-Baden,FRG,pp.85-89.R.D I F RANCESCO(1990).Real-time speech segmentation using pitch and convexity jump models:applica-tion to variable rate speech coding.IEEE Trans.Acoustics,Speech,Signal Processing,vol.ASSP-38,no5, pp.741-748.X.D ING and P.M.F RANK(1990).Fault detection via factorization approach.Systems and Control Letters, vol.14,pp.431-436.J.L.D OOB(1953).Stochastic Processes.Wiley,New York.V.D RAGALIN(1988).Asymptotic solutions in detecting a change in distribution under an unknown param-eter.Statistical Problems of Control,Issue83,Vilnius,pp.45-52.B.D UBUISSON(1990).Diagnostic et Reconnaissance des Formes.Trait´e des Nouvelles Technologies,S´e rie Diagnostic et Maintenance,Herm`e s,Paris(in French).A.J.D UNCAN(1986).Quality Control and Industrial Statistics,5th edition.Richard D.Irwin,Inc.,Home-wood,IL.J.D URBIN(1971).Boundary-crossing probabilities for the Brownian motion and Poisson processes and techniques for computing the power of the Kolmogorov-Smirnov test.Jal Applied Probability,vol.8,pp.431-453.J.D URBIN(1985).Thefirst passage density of the crossing of a continuous Gaussian process to a general boundary.Jal Applied Probability,vol.22,no1,pp.99-122.A.E MAMI-N AEINI,M.M.A KHTER and S.M.R OCK(1988).Effect of model uncertainty on failure detec-tion:the threshold selector.IEEE Trans.Automatic Control,vol.AC-33,no12,pp.1106-1115.J.D.E SARY,F.P ROSCHAN and D.W.W ALKUP(1967).Association of random variables with applications. Annals Mathematical Statistics,vol.38,pp.1466-1474.W.D.E WAN and K.W.K EMP(1960).Sampling inspection of continuous processes with no autocorrelation between successive results.Biometrika,vol.47,pp.263-280.G.F AVIER and A.S MOLDERS(1984).Adaptive smoother-predictors for tracking maneuvering targets.Proc. 23rd Conf.Decision and Control,Las Vegas,NV,pp.831-836.W.F ELLER(1966).An Introduction to Probability Theory and Its Applications,vol.2.Series in Probability and Mathematical Statistics,Wiley,New York.R.A.F ISHER(1925).Theory of statistical estimation.Proc.Cambridge Philosophical Society,vol.22, pp.700-725.M.F ISHMAN(1988).Optimization of the algorithm for the detection of a disorder,based on the statistic of exponential smoothing.In Statistical Problems of Control,Issue83,Vilnius,pp.146-151.R.F LETCHER(1980).Practical Methods of Optimization,2volumes.Wiley,New York.P.M.F RANK(1990).Fault diagnosis in dynamic systems using analytical and knowledge based redundancy -A survey and new results.Automatica,vol.26,pp.459-474.430B IBLIOGRAPHY P.M.F RANK(1991).Enhancement of robustness in observer-based fault detection.Proc.SAFEPRO-CESS’91,Baden-Baden,FRG,pp.275-287.P.M.F RANK and J.W¨UNNENBERG(1989).Robust fault diagnosis using unknown input observer schemes. In Fault Diagnosis in Dynamic Systems-Theory and Application(R.Patton,P.Frank,R.Clark,eds.). International Series in Systems and Control Engineering,Prentice Hall International,London,UK,pp.47-98.K.F UKUNAGA(1990).Introduction to Statistical Pattern Recognition,2d ed.Academic Press,New York. S.I.G ASS(1958).Linear Programming:Methods and Applications.McGraw Hill,New York.W.G E and C.Z.F ANG(1989).Extended robust observation approach for failure isolation.Int.Jal Control, vol.49,no5,pp.1537-1553.W.G ERSCH(1986).Two applications of parametric time series modeling methods.In Mechanical Signature Analysis-Theory and Applications(S.Braun,ed.),chap.10.Academic Press,London.J.J.G ERTLER(1988).Survey of model-based failure detection and isolation in complex plants.IEEE Control Systems Magazine,vol.8,no6,pp.3-11.J.J.G ERTLER(1991).Analytical redundancy methods in fault detection and isolation.Proc.SAFEPRO-CESS’91,Baden-Baden,FRG,pp.9-22.B.K.G HOSH(1970).Sequential Tests of Statistical Hypotheses.Addison-Wesley,Cambridge,MA.I.N.G IBRA(1975).Recent developments in control charts techniques.Jal Quality Technology,vol.7, pp.183-192.J.P.G ILMORE and R.A.M C K ERN(1972).A redundant strapdown inertial reference unit(SIRU).Jal Space-craft,vol.9,pp.39-47.M.A.G IRSHICK and H.R UBIN(1952).A Bayes approach to a quality control model.Annals Mathematical Statistics,vol.23,pp.114-125.A.L.G OEL and S.M.W U(1971).Determination of the ARL and a contour nomogram for CUSUM charts to control normal mean.Technometrics,vol.13,no2,pp.221-230.P.L.G OLDSMITH and H.W HITFIELD(1961).Average run lengths in cumulative chart quality control schemes.Technometrics,vol.3,pp.11-20.G.C.G OODWIN and K.S.S IN(1984).Adaptive Filtering,Prediction and rmation and System Sciences Series,Prentice Hall,Englewood Cliffs,NJ.R.M.G RAY and L.D.D AVISSON(1986).Random Processes:a Mathematical Approach for Engineers. Information and System Sciences Series,Prentice Hall,Englewood Cliffs,NJ.C.G UEGUEN and L.L.S CHARF(1980).Exact maximum likelihood identification for ARMA models:a signal processing perspective.Proc.1st EUSIPCO,Lausanne.D.E.G USTAFSON, A.S.W ILLSKY,J.Y.W ANG,M.C.L ANCASTER and J.H.T RIEBWASSER(1978). ECG/VCG rhythm diagnosis using statistical signal analysis.Part I:Identification of persistent rhythms. Part II:Identification of transient rhythms.IEEE Trans.Biomedical Engineering,vol.BME-25,pp.344-353 and353-361.F.G USTAFSSON(1991).Optimal segmentation of linear regression parameters.Proc.IFAC/IFORS Symp. Identification and System Parameter Estimation,Budapest,pp.225-229.T.H¨AGGLUND(1983).New Estimation Techniques for Adaptive Control.Ph.D.Thesis,Lund Institute of Technology,Lund,Sweden.T.H¨AGGLUND(1984).Adaptive control of systems subject to large parameter changes.Proc.IFAC9th World Congress,Budapest.B IBLIOGRAPHY431 P.H ALL and C.C.H EYDE(1980).Martingale Limit Theory and its Application.Probability and Mathemat-ical Statistics,a Series of Monographs and Textbooks,Academic Press,New York.W.J.H ALL,R.A.W IJSMAN and J.K.G HOSH(1965).The relationship between sufficiency and invariance with applications in sequential analysis.Ann.Math.Statist.,vol.36,pp.576-614.E.J.H ANNAN and M.D EISTLER(1988).The Statistical Theory of Linear Systems.Series in Probability and Mathematical Statistics,Wiley,New York.J.D.H EALY(1987).A note on multivariate CuSum procedures.Technometrics,vol.29,pp.402-412.D.M.H IMMELBLAU(1970).Process Analysis by Statistical Methods.Wiley,New York.D.M.H IMMELBLAU(1978).Fault Detection and Diagnosis in Chemical and Petrochemical Processes. Chemical Engineering Monographs,vol.8,Elsevier,Amsterdam.W.G.S.H INES(1976a).A simple monitor of a system with sudden parameter changes.IEEE r-mation Theory,vol.IT-22,no2,pp.210-216.W.G.S.H INES(1976b).Improving a simple monitor of a system with sudden parameter changes.IEEE rmation Theory,vol.IT-22,no4,pp.496-499.D.V.H INKLEY(1969).Inference about the intersection in two-phase regression.Biometrika,vol.56,no3, pp.495-504.D.V.H INKLEY(1970).Inference about the change point in a sequence of random variables.Biometrika, vol.57,no1,pp.1-17.D.V.H INKLEY(1971).Inference about the change point from cumulative sum-tests.Biometrika,vol.58, no3,pp.509-523.D.V.H INKLEY(1971).Inference in two-phase regression.Jal American Statistical Association,vol.66, no336,pp.736-743.J.R.H UDDLE(1983).Inertial navigation system error-model considerations in Kalmanfiltering applica-tions.In Control and Dynamic Systems(C.T.Leondes,ed.),Academic Press,New York,pp.293-339.J.S.H UNTER(1986).The exponentially weighted moving average.Jal Quality Technology,vol.18,pp.203-210.I.A.I BRAGIMOV and R.Z.K HASMINSKII(1981).Statistical Estimation-Asymptotic Theory.Applications of Mathematics Series,vol.16.Springer,New York.R.I SERMANN(1984).Process fault detection based on modeling and estimation methods-A survey.Auto-matica,vol.20,pp.387-404.N.I SHII,A.I WATA and N.S UZUMURA(1979).Segmentation of nonstationary time series.Int.Jal Systems Sciences,vol.10,pp.883-894.J.E.J ACKSON and R.A.B RADLEY(1961).Sequential and tests.Annals Mathematical Statistics, vol.32,pp.1063-1077.B.J AMES,K.L.J AMES and D.S IEGMUND(1988).Conditional boundary crossing probabilities with appli-cations to change-point problems.Annals Probability,vol.16,pp.825-839.M.K.J EERAGE(1990).Reliability analysis of fault-tolerant IMU architectures with redundant inertial sen-sors.IEEE Trans.Aerospace and Electronic Systems,vol.AES-5,no.7,pp.23-27.N.L.J OHNSON(1961).A simple theoretical approach to cumulative sum control charts.Jal American Sta-tistical Association,vol.56,pp.835-840.N.L.J OHNSON and F.C.L EONE(1962).Cumulative sum control charts:mathematical principles applied to their construction and use.Parts I,II,III.Industrial Quality Control,vol.18,pp.15-21;vol.19,pp.29-36; vol.20,pp.22-28.432B IBLIOGRAPHY R.A.J OHNSON and M.B AGSHAW(1974).The effect of serial correlation on the performance of CUSUM tests-Part I.Technometrics,vol.16,no.1,pp.103-112.H.L.J ONES(1973).Failure Detection in Linear Systems.Ph.D.Thesis,Dept.Aeronautics and Astronautics, MIT,Cambridge,MA.R.H.J ONES,D.H.C ROWELL and L.E.K APUNIAI(1970).Change detection model for serially correlated multivariate data.Biometrics,vol.26,no2,pp.269-280.M.J URGUTIS(1984).Comparison of the statistical properties of the estimates of the change times in an autoregressive process.In Statistical Problems of Control,Issue65,Vilnius,pp.234-243(in Russian).T.K AILATH(1980).Linear rmation and System Sciences Series,Prentice Hall,Englewood Cliffs,NJ.L.V.K ANTOROVICH and V.I.K RILOV(1958).Approximate Methods of Higher Analysis.Interscience,New York.S.K ARLIN and H.M.T AYLOR(1975).A First Course in Stochastic Processes,2d ed.Academic Press,New York.S.K ARLIN and H.M.T AYLOR(1981).A Second Course in Stochastic Processes.Academic Press,New York.D.K AZAKOS and P.P APANTONI-K AZAKOS(1980).Spectral distance measures between gaussian pro-cesses.IEEE Trans.Automatic Control,vol.AC-25,no5,pp.950-959.K.W.K EMP(1958).Formula for calculating the operating characteristic and average sample number of some sequential tests.Jal Royal Statistical Society,vol.B-20,no2,pp.379-386.K.W.K EMP(1961).The average run length of the cumulative sum chart when a V-mask is used.Jal Royal Statistical Society,vol.B-23,pp.149-153.K.W.K EMP(1967a).Formal expressions which can be used for the determination of operating character-istics and average sample number of a simple sequential test.Jal Royal Statistical Society,vol.B-29,no2, pp.248-262.K.W.K EMP(1967b).A simple procedure for determining upper and lower limits for the average sample run length of a cumulative sum scheme.Jal Royal Statistical Society,vol.B-29,no2,pp.263-265.D.P.K ENNEDY(1976).Some martingales related to cumulative sum tests and single server queues.Stochas-tic Processes and Appl.,vol.4,pp.261-269.T.H.K ERR(1980).Statistical analysis of two-ellipsoid overlap test for real time failure detection.IEEE Trans.Automatic Control,vol.AC-25,no4,pp.762-772.T.H.K ERR(1982).False alarm and correct detection probabilities over a time interval for restricted classes of failure detection algorithms.IEEE rmation Theory,vol.IT-24,pp.619-631.T.H.K ERR(1987).Decentralizedfiltering and redundancy management for multisensor navigation.IEEE Trans.Aerospace and Electronic systems,vol.AES-23,pp.83-119.Minor corrections on p.412and p.599 (May and July issues,respectively).R.A.K HAN(1978).Wald’s approximations to the average run length in cusum procedures.Jal Statistical Planning and Inference,vol.2,no1,pp.63-77.R.A.K HAN(1979).Somefirst passage problems related to cusum procedures.Stochastic Processes and Applications,vol.9,no2,pp.207-215.R.A.K HAN(1981).A note on Page’s two-sided cumulative sum procedures.Biometrika,vol.68,no3, pp.717-719.B IBLIOGRAPHY433 V.K IREICHIKOV,V.M ANGUSHEV and I.N IKIFOROV(1990).Investigation and application of CUSUM algorithms to monitoring of sensors.In Statistical Problems of Control,Issue89,Vilnius,pp.124-130(in Russian).G.K ITAGAWA and W.G ERSCH(1985).A smoothness prior time-varying AR coefficient modeling of non-stationary covariance time series.IEEE Trans.Automatic Control,vol.AC-30,no1,pp.48-56.N.K LIGIENE(1980).Probabilities of deviations of the change point estimate in statistical models.In Sta-tistical Problems of Control,Issue83,Vilnius,pp.80-86(in Russian).N.K LIGIENE and L.T ELKSNYS(1983).Methods of detecting instants of change of random process prop-erties.Automation and Remote Control,vol.44,no10,Part II,pp.1241-1283.J.K ORN,S.W.G ULLY and A.S.W ILLSKY(1982).Application of the generalized likelihood ratio algorithm to maneuver detection and estimation.Proc.American Control Conf.,Arlington,V A,pp.792-798.P.R.K RISHNAIAH and B.Q.M IAO(1988).Review about estimation of change points.In Handbook of Statistics(P.R.Krishnaiah,C.R.Rao,eds.),vol.7,Elsevier,New York,pp.375-402.P.K UDVA,N.V ISWANADHAM and A.R AMAKRISHNAN(1980).Observers for linear systems with unknown inputs.IEEE Trans.Automatic Control,vol.AC-25,no1,pp.113-115.S.K ULLBACK(1959).Information Theory and Statistics.Wiley,New York(also Dover,New York,1968). K.K UMAMARU,S.S AGARA and T.S¨ODERSTR¨OM(1989).Some statistical methods for fault diagnosis for dynamical systems.In Fault Diagnosis in Dynamic Systems-Theory and Application(R.Patton,P.Frank,R. Clark,eds.).International Series in Systems and Control Engineering,Prentice Hall International,London, UK,pp.439-476.A.K USHNIR,I.N IKIFOROV and I.S AVIN(1983).Statistical adaptive algorithms for automatic detection of seismic signals-Part I:One-dimensional case.In Earthquake Prediction and the Study of the Earth Structure,Naouka,Moscow(Computational Seismology,vol.15),pp.154-159(in Russian).L.L ADELLI(1990).Diffusion approximation for a pseudo-likelihood test process with application to de-tection of change in stochastic system.Stochastics and Stochastics Reports,vol.32,pp.1-25.T.L.L A¨I(1974).Control charts based on weighted sums.Annals Statistics,vol.2,no1,pp.134-147.T.L.L A¨I(1981).Asymptotic optimality of invariant sequential probability ratio tests.Annals Statistics, vol.9,no2,pp.318-333.D.G.L AINIOTIS(1971).Joint detection,estimation,and system identifirmation and Control, vol.19,pp.75-92.M.R.L EADBETTER,G.L INDGREN and H.R OOTZEN(1983).Extremes and Related Properties of Random Sequences and Processes.Series in Statistics,Springer,New York.L.L E C AM(1960).Locally asymptotically normal families of distributions.Univ.California Publications in Statistics,vol.3,pp.37-98.L.L E C AM(1986).Asymptotic Methods in Statistical Decision Theory.Series in Statistics,Springer,New York.E.L.L EHMANN(1986).Testing Statistical Hypotheses,2d ed.Wiley,New York.J.P.L EHOCZKY(1977).Formulas for stopped diffusion processes with stopping times based on the maxi-mum.Annals Probability,vol.5,no4,pp.601-607.H.R.L ERCHE(1980).Boundary Crossing of Brownian Motion.Lecture Notes in Statistics,vol.40,Springer, New York.L.L JUNG(1987).System Identification-Theory for the rmation and System Sciences Series, Prentice Hall,Englewood Cliffs,NJ.。

Low Temperature Viscosity Measurements -Lovis for Battery ElectrolytesRelevant for: battery industry, electrochemical research, automotive industryPerform viscosity measurements down to -20 °C with Lovis 2000 M/ME with cooling option. Test even highly corrosive solvents for ion salts by using unbreakable PCTFE capillaries with small filling volumes (110 µL or 450 µL). Handling of the sample inside a glove box filled with inert gas and a hermetically closed system prevent contamination or evaporation of the sample.1 IntroductionSince the introduction of the lithium-ion batteries in 1990, the interest in this technology has emerged steadily, not only for portable devices but also for the automotive industry. Their high energy density as well as outstanding cycle stability are the main reasons for commercial success, but several problems arise with the usage of the most common non-aqueous electrolytes, which contain lithiumhexafluoro-phosphate (LiPF6) as conductive salt and a mixture of cyclic and non-cyclic organic carbonates.In addition to the high purity required of all used solvents (e.g. traces of protic impurities such as water can cause severe deterioration of the cell performance after a short life / cycle time) the cell performance has to be stable over a broad temperature range from arctic to tropical conditions without any significant degradation. Therefore, an exact characterization of newly developed electrolytes at different temperatures is an essential part in the lithium-ion cell research today. These challenges have to be considered for every other upcoming battery systems like magnesium ion cells or sulfur cells, too.Therefore, research companies use different standard electrochemical measurements for monitoring batteries. In this connection viscosity, conductivity and – if required – density measurements of the electrolytes support those investigations.The performance of the charge and discharge rate of a rechargeable battery, that is the ion transport, is characterized by the ion conductivity, which depends on the viscosity and the dielectric constant.The viscosity of the solvent, in which the ion salt is solved, affects the mobility of ions, as shown in the Stokes-Einstein equation; mobility is inversely proportional to the viscosity:r ... radius of the solvated ionBased on those viscosity measurements important conclusions on the wettability of the electrode /electro-lyte interface can be drawn, too. Fast, accurate and reproducible viscosity measurement over a wide temperature range is highly desirable for successful development of new electrolyte systems.This application report shows how the Lovis can be used for electrolyte measurements even at tempera-tures below zero. The Lovis, equipped with coolingoption and in combination with the capillary made of PCTFE, enables measurement of highly corrosive substances over a wide temperature range.2 Instrumentation2.1Lovis 2000 M/ME Microviscometer with Cooling OptionFigure 1: Lovis 2000 M with cooling optionThe Lovis 2000 M/ME Microviscometer measures the rolling time of a ball inside an inclined capillary.Variable inclination angles allow for measurements at different shear rates. Temperature control via Peltier elements is extremely fast and provides utmost accuracy.For measuring at temperatures below zero, the Lovis ME Module can be equipped with a lowtemperature option. In combination with a recirculating cooler, it is possible to measure at temperatures as low as -20 °C (lower temperatures down to -30 °C on request, depending on the cooling liquid of the recirculating cooling, ambient temperature and ambient air humidity).The integrated software calculates the kinematic or dynamic viscosity, provided the sample's density value is known.Figure 2: Lovis PCTFE capillariesWith the PCTFE capillaries it is possible to measure nearly every liquid, also corrosive, aggressive or hazardous solvents and electrolytes.The measuring viscosity of a PCTFE capillary ranges from 0.8 mPa.s to 160 mPa.s.Used material:▪ Capillary: PCTFE short (110 µL) ▪ Capillary diameter: 1.62mm ▪ Ball material: Steel ▪ Ball diameter: 1.5 mm2.3 Additional Equipment▪ Glove box filled with argon.▪Circulation cooler plus insulated hoses. How to set up the cooling is precisely described in the documentation of Lovis 2000 M/ME.3MeasurementAll determinations were performed manually without autosampler. The viscosity measurements were performed in a temperature range from -20 °C to +60 °C with steps of 5 °C or 10 °. For temperature table scans (TTS) two density values at two different reference temperatures were typed in manually in the "Quick Settings" ("Lovis Density TS/TTS") for every sample. The instrument automatically extrapolated the missing temperature / density values by linearextrapolation. The density values for the manual input were determined with the SVM™.Every scan was performed twice in order to obtain a repeat determination. To check the reproducibility, all measurements were performed with Lovis and SVM™ in parallel.3.1 Samples▪Different mixtures of organic carbonates, which contain lithiumhexafluorophosphate as conductive salt – for lithium ion batteries (LIB), either commercial available standardelectrolytes or newly developed electrolyte solutions.▪Solvents containing a polar organic solvent and dioxolane added with Li-sulfur-compounds as conductive salts – for future Li-S-cell systems (LiS).▪Solvents containing a polar organic solvent plus Mg-compounds as conductive salts – for prospective Mg-ion batteries.3.2 Instrument Settings Measuring Method: Temperature Table Scan (TTS) Measuring Settings:▪ Temperature: scan between -20 °C to +60 °C ▪ Equilibration Time: no ▪ Measurement Cycles: 3▪ Measuring Angle: Auto Angle * ▪ Variation Coefficient:0.4 % for standard electrolytes ▪ Measuring Distance: Short* Adjustment was performed over an angle range from of 20° to 70° in 10° steps3.3 Filling of the CapillaryAll samples were manually filled in an argon glove box under inert conditions. For each measurement a new steel ball was used to avoid any cross contamination from one measurement to the other. After closing the capillary with the appropriate plug, the hermetically sealed capillary was removed from the glove box.3.4 CleaningThe capillary was cleaned thoroughly with smallbrushes after every test sequence. Ethanol, deionized water and other appropriate solvents were used as cleaning liquids. If necessary, the capillary was placed into an ultrasonic bath (approximately 10 to 20 min, 30 °C, water plus standard detergent). Afterwards the capillary was dried under a pressure-less nitrogen stream.4 ResultsFigure 3: Reproducibility check; standard Li-ion electrolyte V24 measured with Lovis and SVM ™ from +20 °C to -20 °C4.4Temperature Profile of Li-polysulfide4.5Checking the Influence of Conducting Salt5ConclusionBy using the Lovis 2000 M/ME equipped with cooling option, it is possible to perform measurements from -20 °C up to +100 °C. In combination with the capillary made of PCTFE even extremely corrosive substances can be measured under hermetically sealed atmosphere. This allows users to measure theviscosity of electrolytes, which might be destroyed or changed in structure by air and/or air humidity.▪ The small capillary sizes require only littlesample volume (starting from 110 µL). ▪ The small diameter of the PCTFE capillary(1.62 mm) enables also the measurement of very low-viscosity samples (viscosity range from 0.8 mPa.s to 160 mPa.s).▪ The cooling option allows for viscositymeasurements down to -20 °C (lowertemperatures down to -30 °C are possible on request and depending on ambient conditions).▪ The closed system avoids any contaminationand evaporation.▪ The variable inclination angle of themeasurement allows for the variation of the shear rate.▪ Lovis 2000 M/ME is highly modular; it can becombined with DMA™ M Density Meters for automated calculation of dynamic andkinematic viscosity. It can also be combined with an Xsample™ sample changer (see Figure 8) for automatic filling and cleaning of the capillary and measurements with high sample throughput.6ReferencesSpecial thanks to DI Gisela Fauler and Ms. Katja Kapper from VARTA Micro Innovation GmbH who tested the Lovis with cooling option and the PCTFE capillaries and supported Anton Paar with their measurement data.Contact Anton Paar GmbH Tel: +43 316 257-0****************************|。

INTERNATIONAL JOURNAL OF CIRCUIT THEORY AND APPLICATIONSInt.J.Circ.Theor.Appl.2006;34:559–582Published online in Wiley InterScience().DOI:10.1002/cta.375A wavelet-based piecewise approach for steady-state analysisof power electronics circuitsK.C.Tam,S.C.Wong∗,†and C.K.TseDepartment of Electronic and Information Engineering,Hong Kong Polytechnic University,Hong KongSUMMARYSimulation of steady-state waveforms is important to the design of power electronics circuits,as it reveals the maximum voltage and current stresses being imposed upon specific devices and components.This paper proposes an improved approach tofinding steady-state waveforms of power electronics circuits based on wavelet approximation.The proposed method exploits the time-domain piecewise property of power electronics circuits in order to improve the accuracy and computational efficiency.Instead of applying one wavelet approximation to the whole period,several wavelet approximations are applied in a piecewise manner tofit the entire waveform.This wavelet-based piecewise approximation approach can provide very accurate and efficient solution,with much less number of wavelet terms,for approximating steady-state waveforms of power electronics circuits.Copyright2006John Wiley&Sons,Ltd.Received26July2005;Revised26February2006KEY WORDS:power electronics;switching circuits;wavelet approximation;steady-state waveform1.INTRODUCTIONIn the design of power electronics systems,knowledge of the detailed steady-state waveforms is often indispensable as it provides important information about the likely maximum voltage and current stresses that are imposed upon certain semiconductor devices and passive compo-nents[1–3],even though such high stresses may occur for only a brief portion of the switching period.Conventional methods,such as brute-force transient simulation,for obtaining the steady-state waveforms are usually time consuming and may suffer from numerical instabilities, especially for power electronics circuits consisting of slow and fast variations in different parts of the same waveform.Recently,wavelets have been shown to be highly suitable for describingCorrespondence to:S.C.Wong,Department of Electronic and Information Engineering,Hong Kong Polytechnic University,Hunghom,Hong Kong.†E-mail:enscwong@.hkContract/sponsor:Hong Kong Research Grants Council;contract/grant number:PolyU5237/04ECopyright2006John Wiley&Sons,Ltd.560K.C.TAM,S.C.WONG AND C.K.TSEwaveforms with fast changing edges embedded in slowly varying backgrounds[4,5].Liu et al.[6] demonstrated a systematic algorithm for approximating steady-state waveforms arising from power electronics circuits using Chebyshev-polynomial wavelets.Moreover,power electronics circuits are piecewise varying in the time domain.Thus,approx-imating a waveform with one wavelet approximation(ing one set of wavelet functions and hence one set of wavelet coefficients)is rather inefficient as it may require an unnecessarily large wavelet set.In this paper,we propose a piecewise approach to solving the problem,using as many wavelet approximations as the number of switch states.The method yields an accurate steady-state waveform descriptions with much less number of wavelet terms.The paper is organized as follows.Section2reviews the systematic(standard)algorithm for approximating steady-state waveforms using polynomial wavelets,which was proposed by Liu et al.[6].Section3describes the procedure and formulation for approximating steady-state waveforms of piecewise switched systems.In Section4,application examples are presented to evaluate and compare the effectiveness of the proposed piecewise wavelet approximation with that of the standard wavelet approximation.Finally,we give the conclusion in Section5.2.REVIEW OF WA VELET APPROXIMATIONIt has been shown that wavelet approximation is effective for approximating steady-state waveforms of power electronics circuits as it takes advantage of the inherent nature of wavelets in describing fast edges which have been embedded in slowly moving backgrounds[6].Typically,power electronics circuits can be represented by a time-varying state-space equation˙x=A(t)x+U(t)(1) where x is the m-dim state vector,A(t)is an m×m time-varying matrix,and U is the inputfunction.Specifically,we writeA(t)=⎡⎢⎢⎢⎣a11(t)a12(t)···a1m(t)............a m1(t)a m2(t)···a mm(t)⎤⎥⎥⎥⎦(2)andU(t)=⎡⎢⎢⎢⎣u1(t)...u m(t)⎤⎥⎥⎥⎦(3)In the steady state,the solution satisfiesx(t)=x(t+T)for0 t T(4) where T is the period.For an appropriate translation and scaling,the boundary condition can be mapped to the closed interval[−1,1]x(+1)=x(−1)(5) Copyright2006John Wiley&Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582A WA VELET-BASED PIECEWISE APPROACH FOR STEADY-STATE ANALYSIS561 Assume that the basic time-invariant approximation equation isx i(t)=K T i W(t)for−1 t 1and i=1,2,...,m(6) where W(t)is any wavelet basis of size2n+1+1(n being the wavelet level),K T i=[k i,0,...,k i,2n+1] is a coefficient vector of dimension2n+1+1,which is to be found.‡The wavelet transformedequation of(1)isKD W=A(t)K W+U(t)(7)whereK=⎡⎢⎢⎢⎢⎢⎢⎢⎣k1,0k1,1···k1,2n+1k2,0k2,1···k2,2n+1............k m,0k m,1···k m,2n+1⎤⎥⎥⎥⎥⎥⎥⎥⎦(8)Thus,(7)can be written generally asF(t)K=−U(t)(9) where F(t)is a m×(2n+1+1)m matrix and K is a(2n+1+1)m-dim vector,given byF(t)=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣a11(t)W T(t)−W T(t)D T···a1i(t)W T(t)···a1m W T(t)...............a i1(t)W T(t)···a ii(t)W T(t)−W T(t)D T···a im W T(t)...............a m1(t)W T(t)···a mi(t)W T(t)···a mm W T(t)−W T(t)D T⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦(10)K=[K T1···K T m]T(11)Note that since the unknown K is of dimension(2n+1+1)m,we need(2n+1+1)m equations. Now,the boundary condition(5)provides m equations,i.e.[W(+1)−W(−1)]T K i=0for i=1,...,m(12) This equation can be easily solved by applying an appropriate interpolation technique or via direct numerical convolution[11].Liu et al.[6]suggested that the remaining2n+1m equations‡The construction of wavelet basis has been discussed in detail in Reference[6]and more formally in Reference[7].For more details on polynomial wavelets,see References[8–10].Copyright2006John Wiley&Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582562K.C.TAM,S.C.WONG AND C.K.TSEare obtained by interpolating at2n+1distinct points, i,in the closed interval[−1,1],and the interpolation points can be chosen arbitrarily.Then,the approximation equation can be written as˜FK=˜U(13)where˜F= ˜F1˜F2and˜U=˜U1˜U2(14)with˜F1,˜F2,˜U1and˜U2given by˜F1=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣[W(+1)−W(−1)]T(00···0)···(00···0)(00···0)[W(+1)−W(−1)]T···(00···0)............(00···0)2n+1+1columns(00···0)···[W(+1)−W(−1)]T(2n+1+1)m columns⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎫⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭m rows(15)˜F2=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎣F( 1)F( 2)...F( 2n+1)(2n+1+1)m columns⎤⎥⎥⎥⎥⎥⎥⎥⎥⎦⎫⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎭2n+1m rows(16)˜U1=⎡⎢⎢⎢⎣...⎤⎥⎥⎥⎦⎫⎪⎪⎪⎬⎪⎪⎪⎭m elements(17)˜U2=⎡⎢⎢⎢⎢⎢⎣−U( 1)−U( 2)...−U( 2n+1)⎤⎥⎥⎥⎥⎥⎦⎫⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎭2n+1m elements(18)Finally,by solving(13),we obtain all the coefficients necessary for generating an approximate solution for the steady-state system.Copyright2006John Wiley&Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582A WA VELET-BASED PIECEWISE APPROACH FOR STEADY-STATE ANALYSIS5633.WA VELET-BASED PIECEWISE APPROXIMATION METHODAlthough the above standard algorithm,given in Reference[6],provides a well approximated steady-state solution,it does not exploit the piecewise switched nature of power electronics circuits to ease computation and to improve accuracy.Power electronics circuits are defined by a set of linear differential equations governing the dynamics for different intervals of time corresponding to different switch states.In the following,we propose a wavelet approximation algorithm specifically for treating power electronics circuits.For each interval(switch state),we canfind a wavelet representation.Then,a set of wavelet representations for all switch states can be‘glued’together to give a complete steady-state waveform.Formally,consider a p-switch-state converter.We can write the describing differential equation, for switch state j,as˙x j=A j x+U j for j=1,2,...,p(19) where A j is a time invariant matrix at state j.Equation(19)is the piecewise state equation of the system.In the steady state,the solution satisfies the following boundary conditions:x j−1(T j−1)=x j(0)for j=2,3,...,p(20) andx1(0)=x p(T p)(21)where T j is the time duration of state j and pj=1T j=T.Thus,mapping all switch states to the close interval[−1,1]in the wavelet space,the basic approximate equation becomesx j,i(t)=K T j,i W(t)for−1 t 1(22) with j=1,2,...,p and i=1,2,...,m,where K T j,i=[k1,i,0···k1,i,2n+1,k2,i,0···k2,i,2n+1,k j,i,0···k j,i,2n+1]is a coefficient vector of dimension(2n+1+1)×p,which is to be found.Asmentioned previously,the state equation is transformed to the wavelet space and then solved by using interpolation.The approximation equation is˜F(t)K=−˜U(t)(23) where˜F=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣˜F˜F1˜F2...˜Fp⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦and˜U=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣˜U˜U1˜U2...˜Up⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦(24)Copyright2006John Wiley&Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582564K.C.TAM,S.C.WONG AND C.K.TSEwith ˜F0,˜F 1,˜F 2,˜F p ,˜U 0,˜U 1,˜U 2and ˜U p given by ˜F 0=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣F a 00···F b F b F a 0···00F b F a ···0...............00···F b F a (2n +1+1)×m ×p columns⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎫⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭m ×p rows (F a and F b are given in (33)and (34))(25)˜F 1=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣F ( 1)0 0F ( 2)0 0............F ( 2n +1) (2n +1+1)m columns 0(2n +1+1)m columns···0 (2n +1+1)m columns(2n +1+1)×m ×p columns⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎫⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭2n +1m rows(26)˜F 2=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎣0F ( 1)···00F ( 2)···0............0(2n +1+1)m columnsF ( 2n +1)(2n +1+1)m columns···(2n +1+1)m columns⎤⎥⎥⎥⎥⎥⎥⎥⎥⎦(27)˜F p =⎡⎢⎢⎢⎢⎢⎢⎢⎢⎣0···0F ( 1)0···0F ( 2)...... 0(2n +1+1)m columns···(2n +1+1)m columnsF ( 2n +1)(2n +1+1)m columns⎤⎥⎥⎥⎥⎥⎥⎥⎥⎦(28)˜U0=⎡⎢⎢⎢⎣0 0⎤⎥⎥⎥⎦⎫⎪⎪⎪⎬⎪⎪⎪⎭m ×p elements(29)Copyright 2006John Wiley &Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582A WA VELET-BASED PIECEWISE APPROACH FOR STEADY-STATE ANALYSIS565˜U1=⎡⎢⎢⎢⎢⎢⎣−U( 1)−U( 2)...−U( 2n+1)⎤⎥⎥⎥⎥⎥⎦⎫⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎭2n+1m elements(30)˜U2=⎡⎢⎢⎢⎢⎣−U( 1)−U( 2)...−U( 2n+1)⎤⎥⎥⎥⎥⎦(31)˜Up=⎡⎢⎢⎢⎢⎢⎣−U( 1)−U( 2)...−U( 2n+1)⎤⎥⎥⎥⎥⎥⎦(32)F a=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣[W(−1)]T0 00[W(−1)]T 0............00···[W(−1)]T(2n+1+1)m columns⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎫⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭m rows(33)F b=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣[−W(+1)]T0 00[−W(+1)]T 0............00···[−W(+1)]T(2n+1+1)m columns⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎫⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭m rows(34)Similar to the standard approach outlined in Section2,all the coefficients necessary for gener-ating approximate solutions for each switch state for the steady-state system can be obtained by solving(23).It should be noted that the wavelet-based piecewise method can be further enhanced for approx-imating steady-state solution using different wavelet levels for different switch states.Essentially, Copyright2006John Wiley&Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582566K.C.TAM,S.C.WONG AND C.K.TSEwavelets of high levels should only be needed to represent waveforms in switch states where high-frequency details are present.By using different choices of wavelet levels for different switch states,solutions can be obtained more quickly.Such an application of varying wavelet levels for different switch intervals can be easily incorporated in the afore-described algorithm.4.APPLICATION EXAMPLESIn this section,we present four examples to demonstrate the effectiveness of our proposed wavelet-based piecewise method for steady-state analysis of switching circuits.The results will be evaluated using the mean relative error (MRE)and mean absolute error (MAE),which are defined byMRE =12 1−1ˆx (t )−x (t )x (t )d t (35)MAE =12 1−1|ˆx (t )−x (t )|d t (36)where ˆx (t )is the wavelet-approximated value and x (t )is the SPICE simulated result.The SPICE result,being generated from exact time-domain simulation of the actual circuit at device level,can be used for comparison and evaluation.In discrete forms,MAE and MRE are simply given byMRE =1N Ni =1ˆx i −x i x i(37)MAE =1N Ni =1|ˆx i −x i |(38)where N is the total number of points sampled along the interval [−1,1]for error calculation.In the following,we use uniform sampling (i.e.equal spacing)with N =1001,including boundary points.4.1.Example 1:a single pulse waveformConsider the single pulse waveform shown in Figure 1.This is an example of a waveform that cannot be efficiently approximated by the standard wavelet algorithm.The waveform consists of five segments corresponding to five switch states (S1–S5),and the corresponding state equations are given by (19),where A j and U j are given specifically asA j =⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩0if 0 t <t 10if t 1 t <t 21if t 2 t <t 30if t 3 t <t 40if t 4 t T(39)Copyright 2006John Wiley &Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582A WA VELET-BASED PIECEWISE APPROACH FOR STEADY-STATE ANALYSIS567S1S2S3S4S50t1t2t3t4THFigure 1.A single pulse waveform consisting of 5switch states.andU j =⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩0if 0 t <t 1H /(t 2−t 1)if t 1 t <t 2−Hif t 2 t <t 3−H /(t 4−t 3)if t 3 t <t 40if t 4 t T(40)where H is the amplitude (see Figure 1).Switch states 2(S2)and 4(S4)correspond to the rising edge and falling edge,respectively.Obviously,when the widths of rising and falling edges are small (relative to the whole switching period),the standard wavelet method cannot provide a satisfactory approximation for this waveform unless very high wavelet levels are used.Theoretically,the entire pulse-like waveform can be very accurately approximated by a very large number of wavelet terms,but the computational efforts required are excessive.As mentioned before,since the piecewise approach describes each switch interval separately,it yields an accurate steady-state waveform description for each switch interval with much less number of wavelet terms.Figures 2(a)and (b)compare the approximated pulse waveforms using the proposed wavelet-based piecewise method and the standard wavelet method for two different choices of wavelet levels with different widths of rising and falling edges.This example clearly shows the benefits of the wavelet-based piecewise approximation using separate sets of wavelet coefficients for the different switch states.Copyright 2006John Wiley &Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582568K.C.TAM,S.C.WONG AND C.K.TSE0−0.2−0.4−0.6−0.8−1−20−15−10−50.20.40.60.81−0.2−0.4−0.6−0.8−10.20.40.60.81(a)051015(b)Figure 2.Approximated pulse waveforms with amplitude 10.Dotted line is the standard wavelet approx-imated waveforms using wavelets of levels from −1to 5.Solid lines are the actual waveforms and the wavelet-based piecewise approximated waveforms using wavelets of levels from −1to 1:(a)switch states 2and 4with rising and falling times both equal to 5per cent of the period;and (b)switch states 2and 4with rising and falling times both equal to 1per cent of the period.4.2.Example 2:simple buck converterThe second example is the simple buck converter shown in Figure 3.Suppose the switch has a resistance of R s when it is turned on,and is practically open-circuit when it is turned off.The diode has a forward voltage drop of V f and an on-resistance of R d .The on-time and off-time equivalent circuits are shown in Figure 4.The basic system equation can be readily found as˙x=A (t )x +U (t )(41)where x =[i L v o ]T ,and A (t )and U (t )are given byA (t )=⎡⎢⎣−R d s (t )L −1L 1C −1RC⎤⎥⎦(42)U (t )=⎡⎣E (1−s (t ))+V f s (t )L⎤⎦(43)Copyright 2006John Wiley &Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582Figure3.Simple buck convertercircuit.Figure4.Equivalent linear circuits of the buck converter:(a)during on time;and(b)during off time.Table ponent and parameter values for simulationof the simple buck converter.Component/parameter ValueMain inductance,L0.5mHCapacitance,C0.1mFLoad resistance,R10Input voltage,E100VDiode forward drop,V f0.8VSwitching period,T100 sOn-time,T D40 sSwitch on-resistance,R s0.001Diode on-resistance,R d0.001with s(t)defined bys(t)=⎧⎪⎨⎪⎩0for0 t T D1for T D t Ts(t−T)for all t>T(44)We have performed waveform approximations using the standard wavelet method and the proposed wavelet-based piecewise method.The circuit parameters are shown in Table I.We also generate waveforms from SPICE simulations which are used as references for comparison. The approximated inductor current is shown in Figure5.Simple visual inspection reveals that the wavelet-based piecewise approach always gives more accurate waveforms than the standard method.Copyright2006John Wiley&Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582−0.5−10.51−0.5−10.51012345670123456712345671234567(a)(b)(c)(d)Figure 5.Inductor current waveforms of the buck converter.Solid line is waveform from piecewise wavelet approximation,dotted line is waveform from SPICE simulation and dot-dashed line is waveform using standard wavelet approximation.Note that the solid lines are nearly overlapping with the dotted lines:(a)using wavelets of levels from −1to 0;(b)using wavelets of levels from −1to 1;(c)using wavelets oflevels from −1to 4;and (d)using wavelets of levels from −1to 5.Table parison of MREs for approximating waveforms for the simple buck converter.Wavelet Number of MRE for i L MRE for v C CPU time (s)MRE for i L MRE for v C CPU time (s)levels wavelets (standard)(standard)(standard)(piecewise)(piecewise)(piecewise)−1to 030.9773300.9802850.0150.0041640.0033580.016−1to 150.2501360.1651870.0160.0030220.0024000.016−1to 290.0266670.0208900.0320.0030220.0024000.046−1to 3170.1281940.1180920.1090.0030220.0024000.110−1to 4330.0593070.0538670.3750.0030220.0024000.407−1to 5650.0280970.025478 1.4380.0030220.002400 1.735−1to 61290.0122120.011025 6.1880.0030220.0024009.344−1to 72570.0043420.00373328.6410.0030220.00240050.453In order to compare the results quantitatively,MREs are computed,as reported in Table II and plotted in Figure 6.Finally we note that the inductor current waveform has been very well approximated by using only 5wavelets of levels up to 1in the piecewise method with extremelyCopyright 2006John Wiley &Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582123456700.10.20.30.40.50.60.70.80.91M R E (m e a n r e l a t i v e e r r o r )Wavelet Levelsinductor current : standard method inductor current : piecewise methodFigure parison of MREs for approximating inductor current for the simple buck converter.small MREs.Furthermore,as shown in Table II,the CPU time required by the standard method to achieve an MRE of about 0.0043for i L is 28.64s,while it is less than 0.016s with the proposed piecewise approach.Thus,we see that the piecewise method is significantly faster than the standard method.4.3.Example 3:boost converter with parasitic ringingsNext,we consider the boost converter shown in Figure 7.The equivalent on-time and off-time circuits are shown in Figure 8.Note that the parasitic capacitance across the switch and the leakage inductance are deliberately included to reveal waveform ringings which are realistic phenomena requiring rather long simulation time if a brute-force time-domain simulation method is used.The state equation of this converter is given by˙x=A (t )x +U (t )(45)where x =[i m i l v s v o ]T ,and A (t )and U (t )are given byA (t )=A 1(1−s (t ))+A 2s (t )(46)U (t )=U 1(1−s (t ))+U 2s (t )(47)Copyright 2006John Wiley &Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582Figure7.Simple boost convertercircuit.Figure8.Equivalent linear circuits of the boost converter including parasitic components:(a)for on time;and(b)for off time.with s(t)defined earlier in(44)andA1=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣−R mL mR mL m00R mL l−R l+R mL l−1L l1C s−1R s C s000−1RC⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦(48)A2=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣−R mR dL mR m R dL m0−R mL m d mR m R dL l−R mR d+R lL l−1L lR mL l d m1C s00R mC(R d+R m)−R mC(R d+R m)0−R+R m+R dC R(R d+R m)⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦(49)Copyright2006John Wiley&Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582U1=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣EL m⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦(50)U2=⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣EL m−R m V fL m d mR m V fL l(R d+R m)−V f R mC(R d m⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦(51)Again we compare the approximated waveforms of the leakage inductor current using the proposed piecewise method and the standard wavelet method.The circuit parameters are listed in Table III.Figures9(a)and(b)show the approximated waveforms using the piecewise and standard wavelet methods for two different choices of wavelet levels.As expected,the piecewise method gives more accurate results with wavelets of relatively low levels.Since the waveform contains a substantial portion where the value is near zero,we use the mean absolute error(MAE)forTable ponent and parameter values for simulation ofthe boost converter.Component/parameter ValueMain inductance,L m200 HLeakage inductance,L l1 HParasitic resistance,R m1MOutput capacitance,C200 FLoad resistance,R10Input voltage,E10VDiode forward drop,V f0.8VSwitching period,T100 sOn-time,T D40 sParasitic lead resistance,R l0.5Switch on-resistance,R s0.001Switch capacitance,C s200nFDiode on-resistance,R d0.001Copyright2006John Wiley&Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–5820−0.2−0.4−0.6−0.8−1−50.20.40.60.815100(a)(b)−50.20.40.60.81510Figure 9.Leakage inductor waveforms of the boost converter.Solid line is waveform from wavelet-based piecewise approximation,dotted line is waveform from SPICE simulation and dot-dashed line is waveform using standard wavelet approximation:(a)using wavelets oflevels from −1to 4;and (b)using wavelets of levels from −1to 5.Table IV .Comparison of MAEs for approximating the leakage inductor currentfor the boost converter.Wavelet Number MAE for i l CPU time (s)MAE for i l CPU time (s)levels of wavelets(standard)(standard)(piecewise)(piecewise)−1to 3170.4501710.1250.2401820.156−1to 4330.3263290.4060.1448180.625−1to 5650.269990 1.6410.067127 3.500−1to 61290.2118157.7970.06399521.656−1to 72570.13254340.6250.063175171.563evaluation.From Table IV and Figure 10,the result clearly verifies the advantage of using the proposed wavelet-based piecewise method.Furthermore,inspecting the two switch states of the boost converter,it is obvious that switch state 2(off-time)is richer in high-frequency details,and therefore should be approximated with wavelets of higher levels.A more educated choice of wavelet levels can shorten the simulationCopyright 2006John Wiley &Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582345670.050.10.150.20.250.30.350.40.450.5M A E (m e a n a b s o l u t e e r r o r )Wavelet Levelsleakage inductor current : standard method leakage inductor current : piecewise methodFigure parison of MAEs for approximating the leakage inductor current for the boost converter.time.Figure 11shows the approximated waveforms with different (more appropriate)choices of wavelet levels for switch states 1(on-time)and 2(off-time).Here,we note that smaller MAEs can generally be achieved with a less total number of wavelets,compared to the case where the same wavelet levels are employed for both switch states.Also,from Table IV,we see that the CPU time required for the standard method to achieve an MAE of about 0.13for i l is 40.625s,while it takes only slightly more than 0.6s with the piecewise method.Thus,the gain in computational speed is significant with the piecewise approach.4.4.Example 4:flyback converter with parasitic ringingsThe final example is a flyback converter,which is shown in Figure 12.The equivalent on-time and off-time circuits are shown in Figure 13.The parasitic capacitance across the switch and the transformer leakage inductance are included to reveal realistic waveform ringings.The state equation of this converter is given by˙x=A (t )x +U (t )(52)where x =[i m i l v s v o ]T ,and A (t )and U (t )are given byA (t )=A 1(1−s (t ))+A 2s (t )(53)U (t )=U 1(1−s (t ))+U 2s (t )(54)Copyright 2006John Wiley &Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–5820−0.2−0.4−0.6−0.8−1−6−4−20.20.40.60.81024680−0.2−0.4−0.6−0.8−1−6−4−20.20.40.60.81024680−0.2−0.4−0.6−0.8−1−6−4−20.20.40.60.81024680−0.2−0.4−0.6−0.8−1−6−4−20.20.40.60.8102468il(A)il(A)il(A)il(A)(a)(b)(c)(d)Figure 11.Leakage inductor waveforms of the boost converter with different choice of wavelet levels for the two switch states.Dotted line is waveform from SPICE simulation.Solid line is waveform using wavelet-based piecewise approximation.Two different wavelet levels,shown in brackets,are used for approximating switch states 1and 2,respectively:(a)(3,4)with MAE =0.154674;(b)(3,5)withMAE =0.082159;(c)(4,5)with MAE =0.071915;and (d)(5,6)with MAE =0.066218.Copyright 2006John Wiley &Sons,Ltd.Int.J.Circ.Theor.Appl.2006;34:559–582。

Probability and Stochastic ProcessesProbability and stochastic processes are important concepts in the field of mathematics and have applications in various areas such as engineering, finance, and computer science. In this response, I will discuss the significance of probability and stochastic processes from multiple perspectives, highlightingtheir practical applications, theoretical foundations, and potential limitations. From a practical perspective, probability and stochastic processes play a crucial role in decision-making under uncertainty. Whether it is predicting the weather, estimating the risk of a financial investment, or designing a reliable communication system, the ability to quantify and analyze uncertainty is essential. Probability theory provides a framework for modeling and analyzing random events, enabling us to make informed decisions based on the likelihood of different outcomes. Stochastic processes, on the other hand, allow us to model systems that evolve over time in a probabilistic manner, providing valuable insights into the behavior of complex systems. In the field of engineering, probability and stochastic processes are used extensively in reliability analysis and system design. By modeling the failure rates of components and the interactions between them, engineers can evaluate the reliability of a system and identify potential weaknesses. This information is crucial for designing robust systems that can withstand uncertainties and minimize the risk of failure. Stochastic processes, such as Markov chains and queuing theory, are also used to model and analyze various engineering systems, including communication networks, manufacturing processes, and transportation systems. From a financial perspective, probability and stochastic processes are essential tools for risk management and investment analysis. Financial markets are inherently uncertain, and understanding the probabilistic nature of asset prices and returns is crucial for making informed investment decisions. By modeling the behavior of financial variables using stochastic processes, such as geometric Brownian motion or jump-diffusion processes, analysts can estimate the probabilities of different market scenarios and assess the risk associated with different investment strategies. This information is invaluable for portfolio management, option pricing, and hedging strategies. From a theoretical perspective, probability theory and stochasticprocesses provide a rigorous mathematical foundation for understanding randomness and uncertainty. Probability theory, with its axioms and theorems, allows us to reason logically about uncertain events and make precise statements about their probabilities. Stochastic processes, as mathematical models for random phenomena, provide a framework for studying the long-term behavior of systems and analyzing their statistical properties. This theoretical understanding is not only important for practical applications but also for advancing our knowledge in various scientific disciplines, including physics, biology, and social sciences. However, it is important to acknowledge the limitations of probability and stochastic processes. Firstly, these concepts are based on assumptions and simplifications that may not always hold in real-world situations. For example, many stochastic models assume that the underlying processes are stationary and independent, which may not be true in practice. Secondly, probability and stochastic processes can only provide probabilistic predictions and estimates, rather than deterministic outcomes. This inherent uncertainty means that even with the best models and data, there will always be a degree of unpredictability. Lastly, the accuracy of probability and stochastic models heavily relies on the availability and quality of data. In situations where data is limited or unreliable, the predictions and estimates obtained from these models may be less accurate or even misleading. In conclusion, probability and stochastic processes are fundamental concepts with wide-ranging applications and theoretical significance. They provide a powerful framework for quantifying and analyzing uncertainty, enabling us to make informed decisions and understand the behavior of complex systems. From practical applications in engineering and finance to theoretical foundations in mathematics and science, probability and stochastic processes play a crucial role in our understanding of the world. However, it is important to recognize theirlimitations and the inherent uncertainties they entail. By embracing uncertainty and using probability and stochastic processes as tools for reasoning anddecision-making, we can navigate the complexities of the world with greater confidence and understanding.。

a rXiv:q uant-ph/0382v131J u l23Classical MotionRichard Mould ∗Abstract Preciously given rules allow conscious systems to be included in quan-tum mechanical systems.There rules are derived from the empirical ex-perience of an observer who witnesses a quantum mechanical interaction leading to the capture of a single particle.In the present paper it is shown that purely classical changes experienced by an observer are consistent with these rules.Three different interactions are considered,two of which combine classical and quantum mechanical changes.The previously given rules support all of these cases.Introduction In a previous paper [1],drift consciousness refers to the way the conscious attention of an observer moves to nearby states that are distinct from the original state and from each other.In another paper [3],the drift of a conscious pulse is one that moves continuously over brain states.The first is characteristic of quantum mechanical drifting,and the second is characteristic of classical drifting.The first has been dealt with extensively in a number of papers [1]-[5],but the second needs some clarification.The simplest case of classical drifting (i.e.,classical motion)consists of aslow but continuous change of some conscious scene.Imagine that an observer is looking at a red field that is slowly but continuously turning into a green field.At each moment of time the brain is centered on a state that has a definite color,like states a and b at times t 1and t 2in fig.1.The shaded circle centered at point a reflects the range of the conscious pulse at time t 1.It is the observer’s temporal and spatial resolution width at each moment.Each horizontal line in that figure represents a spatial range of states with the same color.Neighborhood states at different times will shade continuously from onegreen states transition states red statesstatesFigure 1color to another,with the leading edge of the pulse being more green,and the trailing edge being more red.The pulse therefore includes states that are all the same color at each moment of time,where each fades continuously into another color as a function of time.If the observer’s experience is more complex at each moment,then that complexity will be reflected in differences among the horizontal states.The most general case of classical motion is therefore represented by fig.2,where each point in the field is a different conscious or (possibly)unconscious state.The only requirement is that the change from one state to the next (horizontally or vertically)is continuous.The result will be the motion of a conscious pulse over a classical scene that is continuous.A classical Hamiltonian does not make discontinuous jumps even though,in some cases,the rateof change might be too fast for the observer to resolve the states within the conscious pulse.t 1t 2Figure 2One might suppose that the brain’s Hamiltonian contains discontinuities that will disrupt the continuity of the field in fig.2.Brain discontinuities include abrupt changes of awareness,including periods of unconsciousness that may2quickly come or go.However,if the brain at every moment is correlated with an environment that is classically continuous,then thefield infig.2will be continuous.Classical Observation of a DetectorPrior to an observer interacting with and becoming aware of a piece of laboratory equipment such as a detector D,the state of the system will take the formΦ(t i>t)=D{X}where{X}is a pulse that includes unspecified conscious or unconscious brain states of the observer prior to interaction,and t i is the time of detector/observer interaction.When the interaction begins,the system evolves toΦ(t≥t i)=D{X}+..+..+D{Bis a conscious brain state (refs.1,5).The brackets around{X}and{B}+D1(t){B1}(2)3where it is assumed that eq.1applies between t i and time t 0.After t 0,there is continuous flow of probability current from the first component to the second in eq.2.However,unlike the interaction in eq.1,the observer continues to be conscious of the first component during this process -until there is a stochas-tic hit on the second component at t sc .At that time the first component in this equation goes to zero and consciousness is conferred on the ready brain pulse {B 1},making it a conscious brain pulse {B0}to atotally different conscious field is shown in fig.3,where the initial conscious pulse is seen (on the left)to approach the interaction time t 0with full strength.After t 0,it weakens and an associated ready brain pulse on the right gains strength;that is,the initial pulse loses amplitude and the ready pulse gains amplitude 1.At time t sc the first component disappears completely and the second component becomes conscious.timet 0t itsc 4 conscious states 1st component:2nd component:2 ready states 2 conscious states1field points include D 0initial field points include D final Figure 3The instantaneous change from the first to the second component in eq.2may seem incorrect when it is noted that the detector (being an macroscopic body)cannot undergo instantaneous change.The detector in eq.2includes all of the low level physiological states of the brain as well as all the process inside of the detector proper.The time dependent function D 1(t )therefore includes all of the above changes,but the observer will only ‘see’the result of the changeswhen the conscious pulse{B}.1 To see this in detail,rewrite eq.2representing the detector in three parts DDD where these are the early,middle,and later parts of the detector.Of course,the detector can be broken up into a continuum of intermediate states between initial andfinal states,but we will simplify with only three.There will then be four components in eq.2.Φ(t sc>t≥t0>t i)=ψ(t)D0D0D0{B0}Subsequently there will be a classical progression(given by the arrows below) that leadsfinally to the observer’s conscious awareness of the capture.Φ(t≥t sc)=D1(t)D0D0{B0}→D′′1(t)D1D1{B}only at the end.In this and other papers,1we will skip these intermediate steps by going directly from thefirst to the last components as in eq.2.Pulse to PulseThefirst component{Bof states does not negate the rule.The Hamiltonian acts on each individual state such as a in the conscious pulse infig.4,to carry a current J aa′from it to the new ready state a′in thatfigure.The conscious pulseFigure4So state a undergoes a discontinuous change to state a′as required by rule(2).A Terminal ObservationIn the case of the terminal observation described in ref.1,the interaction be-tween an incoming particle and a detector is complete by a time t f,which is assumed to be before an observer looks at the apparatus at time t ob.Φ(t ob>t>t f)=[ψ(t)D0+D1(t)]{X}where{X}is an unspecified brain pulse of the observer that is not yet entangled with the detector.At time t i the interaction begins like the one in eq.1,where the unspecified pulse{X}changes classically into a pulse{B}]Initially,the observer will not be able to distinguish between the two super-imposed detector states D0and D1.However,at some point he will resolve the difference between them,and at this point,a continuous“classical”evolu-tion will no longer be possible.Let this happen with thefirst appearance of6state {B}(3)+ψ′(t )D 0{B 0}+D ′1(t ){B 1}Current will flow from ψ(t )D 0{B}in the first row to thesecond component D ′1(t ){B 1}in the second row.It is the flow of current to thetwo ready brain pulses that will lead to a stochastic choice between them.That choice will produce eitherΦ(t ≥t sc )=ψ(t )D 0{B 1}This evolution of the conscious field is shown in fig.5.The initial classical change {X }→{B}diminishes in amplitude as current flows into theready brain states to the right and to the left.It is imagined that a stochastic hit occurs on field points to the left that include the detector state D 0.2nd row:2nd component:field points include D 12nd row:1st component:2 conscious states 4 conscious statesfield points include D 0t t t i4 classical states 1st row:X {}Figure 57ConclusionThe above examples include three very different ways that an observer can interact with a detector.Thefirst(eq.1)occurs when an observer interacts in a purely classical way.The second(eq.2,fig.3)is a quantum mechanical interaction that occurs after the observer is already entangled with the detector. And the third(eq.3,fig.5)is a classical/quantum mechanical interaction that occurs as the observer becomes entangled with a detector superposition.In the second and third cases,quantum mechanical and the classical changes are intermingled in distinctive ways.Generally speaking,if an observer evolves continuously along a single line in afield of possible conscious experiences,then his motion will be classical.A stochastic choice will not be necessary.However,if the observer encounters a superposition,or somehow becomes part of a superposition,then that single line will break into two or more branches.Since the observer cannot be conscious on more than one branch at a time,a stochastic choice must be made to decide which branch will be followed by the conscious observer.When a non-continuous quantum mechanical jump of this kind presents itself,rule(2)requires that the newly emerging state must be a ready brain state.References[1]R.A.Mould,“Consciousness:The rules of engagement”,quant-ph/0206064[2]R.A.Mould,“Schr¨o dinger’s Cat:The rules of engagement”,quant-ph/0206065[3]R.A.Mould,“Conscious Pulse I:The rules of engagement”,quant-ph/0207005[4]R.A.Mould,“Conscious Pulse II:The rules of engagement”,quant-ph/0207165[5]R.A.Mould,“Quantum Brain States”,Found.Phys.33(4)591-612(2003),quant-ph/03030648。

discrete signal 控制-回复Discrete Signal Control: Understanding and ApplicationIntroduction:Discrete signal control refers to the process of utilizing discrete signals, which are signals that take on a limited number of values, in various control systems. These signals are characterized by their ability to be quantized and processed. In this article, we will delve into the world of discrete signal control, exploring its principles, techniques, and applications.1. What is a discrete signal?A discrete signal is a signal that is not continuous but rather characterized by distinct and separate values at specific points in time. Unlike continuous signals, which can take on an infinite number of values within a specific range, discrete signals only assume specific discrete values at specific points in time.Discrete signals are typically represented as sequences of numbers, with each number corresponding to a specific point in time. Thesesequences can either be finite or infinite, depending on the length of the signal.2. Why use discrete signals in control systems?Discrete signals offer several advantages in control systems:a. Simplified representation: Quantizing signals into discrete values allows for simpler representation and storage. It reduces the complexity of signal processing and makes it easier to implement control algorithms.b. Time synchronization: Discrete signals enable accurate synchronization between control systems and the signals they receive. With discrete values representing specific points in time, control systems can react precisely and consistently.c. Noise immunity: Discrete signals can tolerate noise better than continuous signals. By quantizing the signal into discrete values, small fluctuations in the signal can be filtered out, leading to improved system performance and stability.3. Techniques for controlling discrete signals:a. Digital control: Digital control is a popular technique for controlling discrete signals. It involves converting the analog signals received by sensors into digital form for processing and manipulation by microprocessors or digital signal processors (DSPs). Digital control allows for precise and flexible control algorithms, making it ideal for complex control systems.b. Sampling and quantization: Sampling is the process of converting continuous signals into discrete signals by periodically measuring the signal at specific points in time. Quantization, on the other hand, involves assigning discrete values to the measured samples. Together, sampling and quantization allow for the representation and analysis of continuous signals using discrete values.c. Discrete-time control systems: Discrete-time control systems use discrete signals to model and control dynamic systems. These systems operate on sampled signals that are processed at fixed intervals. Discrete-time control systems are widely utilized in various fields, including robotics, automation, andtelecommunications.4. Applications of discrete signal control:a. Robotics: Discrete signal control is extensively used in robotics applications. Robots rely on discrete signals to perceive their environment, process information, and execute commands. Using discrete signals, robots can interact with their surroundings and perform tasks with accuracy and precision.b. Process control: Discrete signal control is crucial in process control systems, where precise control over physical variables is essential for maintaining safety and efficiency. Discrete signals enable the monitoring and adjustment of critical process variables such as temperature, pressure, and flow rate.c. Communication systems: Discrete signals play a vital role in communication systems, including digital signal processing, data transmission, and error detection and correction. By converting continuous signals into discrete signals, information can be encoded, transmitted, and decoded accurately and reliably.Conclusion:Discrete signal control is a fundamental aspect of modern control systems. By leveraging the advantages of discrete signals, such as simplified representation, time synchronization, and noise immunity, control engineers can design and implement robust control algorithms. From robotics to process control and communication systems, discrete signal control finds applications in various fields, revolutionizing the way we interact with technology and enhancing the overall performance and efficiency of control systems.。

Journal of Artificial Intelligence Research27(2006)235–297Submitted03/06;published10/06Modelling Mixed Discrete-Continuous Domains for Planning Maria Fox maria.fox@Derek Long derek.long@ Department of Computer and Information SciencesUniversity of Strathclyde,26Richmond Street,Glasgow,G11XH,UKAbstractIn this paper we present pddl+,a planning domain description language for modelling mixed discrete-continuous planning domains.We describe the syntax and modelling style of pddl+,showing that the language makes convenient the modelling of complex time-dependent effects.We provide a formal semantics for pddl+by mapping planning instances into constructs of hybrid ing the syntax of HAs as our semantic model we construct a semantic mapping to labelled transition systems to complete the formal interpretation of pddl+planning instances.An advantage of building a mapping from pddl+to HA theory is that it forms a bridge between the Planning and Real Time Systems research communities.One consequence is that we can expect to make use of some of the theoretical properties of HAs.For example,for a restricted class of HAs the Reachability problem(which is equivalent to Plan Existence)is decidable.pddl+provides an alternative to the continuous durative action model of pddl2.1, adding a moreflexible and robust model of time-dependent behaviour.1.IntroductionThis paper describes pddl+,an extension of the pddl(McDermott&the AIPS’98Plan-ning Competition Committee,1998;Fox&Long,2003;Hoffmann&Edelkamp,2005)family of deterministic planning modelling languages.pddl+is intended to support the repre-sentation of mixed discrete-continuous planning domains.pddl was developed by McDer-mott(McDermott&the AIPS’98Planning Competition Committee,1998)as a standard modelling language for planning domains.It was later extended(Fox&Long,2003)to allow temporal structure to be modelled under certain restricting assumptions.The result-ing language,pddl2.1,was further extended to include domain axioms and timed initial literals,resulting in pddl2.2(Hoffmann&Edelkamp,2005).In pddl2.1,durative actions withfixed-length duration and discrete effects can be modelled.A limited capability to model continuous change within the durative action framework is also provided.pddl+provides a moreflexible model of continuous change through the use of au-tonomous processes and events.The modelling of continuous processes has also been con-sidered by McDermott(2005),Herrmann and Thielscher(1996),Reiter(1996),Shana-han(1990),Sandewall(1989)and others in the knowledge representation and reasoning communities,as well as by Henzinger(1996),Rasmussen,Larsen and Subramani(2004), Haroud and Faltings(1994)and others in the real time systems and constraint-reasoning communities.Fox&LongThe most frequently used subset of pddl2.1is the fragment modelling discretised change. This is the part used in the3rd International Planning Competition and used as the basis of pddl2.2.The continuous modelling constructs of pddl2.1have not been adopted by the community at large,partly because they are not considered an attractive or natural way to represent certain kinds of continuous change(McDermott,2003a;Boddy,2003).By wrapping up continuous change inside durative actions pddl2.1forces episodes of change on a variable to coincide with logical state changes.An important limitation of the continuous durative actions of pddl2.1is therefore that the planning agent must take full control over all change in the world,so there can be no change without direct action on the part of the agent.The key extension that pddl+provides is the ability to model the interaction between the agent’s behaviour and changes that are initiated by the world.Processes run over time and have a continuous effect on numeric values.They are initiated and terminated either by the direct action of the agent or by events triggered in the world.We refer to this three-part structure as the start-process-stop model.We make a distinction between logical and numeric state,and say that transitions between logical states are instantaneous whilst occupation of a given logical state can endure over time.This approach takes a transition system view of the modelling of change and allows a direct mapping to the languages of the real time systems community where the same modelling approach is used(Yi,Larsen, &Pettersson,1997;Henzinger,1996).In this paper we provide a detailed discussion of the features of pddl+,and the reasons for their addition.We develop a formal semantics for our primitives in terms of a formal mapping between pddl+and Henzinger’s theory of hybrid automata(Henzinger,1996). Henzinger provides the formal semantics of HAs by means of the labelled transition system. We therefore adopt the labelled transition semantics for planning instances by going through this route.We explain what it means for a plan to be valid by showing how a plan can be interpreted as an accepting run through the corresponding labelled transition system.We note that,under certain constraints,the Plan Existence problem for pddl+planning instances(which corresponds to the Reachability problem for the corresponding hybrid au-tomaton)remains decidable.We discuss these constraints and their utility in the modelling of mixed discrete-continuous planning problems.2.MotivationMany realistic contexts in which planning can be applied feature a mixture of discrete and continuous behaviours.For example,the management of a refinery(Boddy&Johnson, 2004),the start-up procedure of a chemical plant(Aylett,Soutter,Petley,Chung,&Ed-wards,2001),the control of an autonomous vehicle(L´e aut´e&Williams,2005)and the coordination of the activities of a planetary lander(Blake et al.,2004)are problems for which reasoning about continuous change is fundamental to the planning process.These problems also contain discrete change which can be modelled through traditional planning formalisms.Such situations motivate the need to model mixed discrete-continuous domains as planning problems.Modelling Mixed Discrete-Continuous Domains for Planning We present two motivating examples to demonstrate how discrete and continuous be-haviours can interact to yield interesting planning problems.These are Boddy and Johnson’s petroleum refinery domain and the battery power model of Beagle2.2.1Petroleum refinery production planningBoddy and Johnson(2004)describe a planning and scheduling problem arising in the man-agement of petroleum refinement operations.The objects of this problem include materials, in the form of hydrocarbon mixtures and fractions,tanks and processing units.During the operation of the refinery the mixtures and fractions pass through a series of processing units including distillation units,desulphurisation units and cracking units.Inside these units they are converted and combined to produce desired materials and to remove waste products.Processes include thefilling and emptying of tanks,which in some cases can happen simultaneously on the same tank,treatment of materials and their transfer between tanks.The continuous components of the problem include process unit control settings,flow volumes and rates,material properties and volumes and the time-dependent properties of materials being combined in tanks as a consequence of refinement operations.An example demonstrating the utility of a continuous model arises in the construction of a gasoline blend.The success of a gasoline blend depends on the chemical balance of its constituents.Blending results from materials being pumped into and out of tanks and pipelines at rates which enable the exact quantities of the required chemical constituents to be controlled.For example,when diluting crude oil with a less sulphrous material the rate of in-flow of the diluting material,and its volume in the tank,have to be balanced by out-flow of the diluted crude oil and perhaps by other refinement operations.Boddy and Johnson treat the problem of planning and scheduling refinery operations as an optimisation problem.Approximations based on discretisation lead to poor solutions, leading to afinancial motivation for Boddy and Johnson’s application.As they observe,a moderately large refinery can produce in the order of half a million barrels per day.They calculate that a1%decrease in efficiency,resulting from approximation,could result in the loss of a quarter of a million dollars per day.The more accurate the model of the continuous dynamics the more efficient and cost-effective the refinery.Boddy and Johnson’s planning and scheduling approach is based on dynamic constraint satisfaction involving continuous,and non-linear,constraints.A domain-specific solver was constructed,demonstrating that direct handling of continuous problem components can be realistic.Boddy and Johnson describe applying their solver to a real problem involv-ing18,000continuous constraints including2,700quadratic constraints,14,000continuous variables and around40discrete decisions(Lamba,Dietz,Johnson,&Boddy,2003;Boddy &Johnson,2002).It is interesting to observe that this scale of problem is solvable,to optimality,with reasonable computational effort.2.2Planning Activities for a Planetary LanderBeagle2,the ill-fated probe intended for the surface of Mars,was designed to operate within tight resource constraints.The constraint on payload mass,the desire to maximise science return and the rigours of the hostile Martian environment combine to make it essential to squeeze high performance from the limited energy and time available during its mission.Fox&LongOne of the tightest constraints on operations is that of energy.On Beagle2,energy was stored in a battery,recharged from solar power and consumed by instruments,the on-board processor,communications equipment and a heater required to protect sensitive components from the extreme cold over Martian nights.These features of Beagle2are common to all deep space planetary landers.The performance of the battery and the solar panels are both subject to variations due to ageing,atmospheric dust conditions and temperature.Nevertheless,with long periods between communication windows,a lander can only achieve dense scientific data-gathering if its activities are carefully planned and this planning must be performed against a nominal model of the behaviour of battery,solar panels and instruments.The state of charge of the battery of the lander falls within an envelope defined by the maximum level of the capacity of the battery and the minimum level dictated by the safety requirements of the lander. This safety requirement ensures there is enough power at nightfall to power the heater through night operations and to achieve the next communications session.All operations change the state of battery charge,causing it to follow a continuous curve within this envelope.In order to achieve a dense performance,the operations of the lander must be pushed into the envelope as tightly as possible.The equations that govern the physical behaviour of the energy curve are complex,but an approximation of them is possible that is both tractable and more accurate than a discretised model of the curve would be.As in the refinery domain,any approximation has a cost:the coarser the approximation of the model,the less accurately it is possible to determine the limits of the performance of a plan.In this paper we refer to a simplified model of this domain,which we call the Planetary Lander Domain.The details of this model are presented in Appendix C,and discussed in Section4.3.2.3RemarksIn these two examples plans must interact with the background continuous behaviours that are triggered by the world.In the refinery domain concurrent episodes of continuous change (such as thefilling and emptying of a tank)affect the same variable(such as the sulphur content of the crude oil in the tank),and theflow into and out of the tank must be carefully controlled to achieve a mixture with the right chemical composition.In the Beagle2domain the power generation and consumption processes act concurrently on the power supply in a way that must be controlled to avoid the supply dropping below the critical minimal threshold.In both domains the continuous processes are subject to discontinuousfirst derivative effects,resulting from events being triggered,actions being executed or processes interacting.When events trigger the discontinuities might not coincide with the end-points of actions.A planner needs an explicit model of how such events might be triggered in order to be able to reason about their effects.We argue that discretisation represents an inappropriate simplification of these domains, and that adequate modelling of the continuous dynamics is necessary to capture their critical features for planning.Modelling Mixed Discrete-Continuous Domains for Planningyout of the PaperIn Section4we explain how pddl+builds on the foundations of the pddl family of lan-guages.We describe the syntactic elements that are new to pddl+and we remind the reader of the representation language used for expressing temporal plans in the family.We develop a detailed example of a domain,the battery power model of a planetary lander, in which continuous modelling is required to properly capture the behaviours with which a plan must interact.We complete this section with a formal proof showing that pddl+is strictly more expressive than pddl2.1.In Section5we explain why the theory of hybrid automata is relevant to our work, and we provide the key automaton constructs that we will use in the development of the semantics of pddl+.In Section6we present the mapping from planning instances to HAs. In doing this we are using the syntactic constructs of the HA as our semantic model.In Section7we discuss the subset of HAs for which the Reachability problem is decidable,and why we might be interested in these models in the context of planning.We conclude the paper with a discussion of related work.4.FormalismIn this section we present the syntactic foundations of pddl+,clarifying how they extend the foregoing line of development of the pddl family of languages.We rely on the definitions of the syntactic structures of pddl2.1,which we call the Core Definitions.These were published in2003(Fox&Long,2003)but we repeat them in Appendix A for ease of reference.pddl+includes the timed initial literal construct of pddl2.2(which provides a syn-tactically convenient way of expressing the class of events that can be predicted from the initial state).Although derived predicates are a powerful modelling concept,they have not so far been included in pddl+.Further work is required to explore the relationship between derived predicates and the start-process-stop model and we do not consider this further in this paper.4.1Syntactic Foundationspddl+builds directly on the discrete fragment of pddl2.1:that is,the fragment contain-ingfixed-length durative actions.This is supplemented with the timed initial literals of pddl2.2(Hoffmann&Edelkamp,2005).It introduces two new constructs:events and pro-cesses.These are represented by similar syntactic frames to actions.The elements of the formal syntax that are relevant are given below(these are to be read in conjunction with the BNF description of pddl2.1given in Fox&Long,2003).<structure-def>::=:events<event-def><structure-def>::=:events<process-def>The following is an event from the Planetary Lander Domain.It models the transition from night to day that occurs when the clock variable daytime reaches zero.Fox&Long(:event daybreak:parameters():precondition(and(not(day))(>=(daytime)0)):effect(day))The BNF for an event is identical to that of actions,while for processes it is modified by allowing only a conjunction of process effects in the effectsfield.A process effect has the same structure as a continuous effect in pddl2.1:<process-effect>::=(<assign-op-t><f-head><f-exp-t>)The following is a process taken from the Planetary Lander Domain.It describes how the battery state of charge,soc,is affected when power demand exceeds supply.The interpretation of process effects is explained in Section4.2.(:process discharging:parameters():precondition(>(demand)(supply)):effect(decrease soc(*#t(-(demand)(supply)))))We now provide the basic abstract syntactic structures that form the core of a pddl+ planning domain and problem and for which our semantic mappings will be constructed. Core Definition1defines a simple planning instance in which actions are the only struc-tures describing state change.Definition1extends Core Definition1to include events and processes.We avoid repeating the parts of the core definition that are unchanged in this extended version.Definition1Planning Instance A planning instance is defined to be a pairI=(Dom,P rob)where Dom=(F s,Rs,As,Es,P s,arity)is a tuple consisting offinite sets of function symbols,relation symbols,actions,and a function arity mapping all of these symbols to their respective arities,as described in Core Definition1.In addition it containsfinite sets of events Es and processes P s.Ground events,E,are defined by the obvious generalisation of Core Definition6which defines ground actions.The fact that events are required to have at least one numeric precondition makes them a special case of actions.The details of ground processes,P,are given in Definition2.Processes have continuous effects on primitive numeric expressions (PNEs).Core Definition1defines PNEs as ground instances of metric function expressions. Definition2Ground Process Each p∈P is a ground process having the following components:•Name The process schema name together with its actual parameters.Modelling Mixed Discrete-Continuous Domains for PlanningTime Action Duration0.01:Action1[13.000]0.01:Action20.71Action30.9Action415.02:Action5[1.000]18.03:Action6[1.000]19.51:Action721.04:Action8[1.000]Figure1:An example of a pddl+plan showing the time stamp and duration associated with each action,where applicable.Actions2,3,4and7are instantaneous,sohave no associated duration.•Precondition This is a proposition,P re p,the atoms of which are either ground atoms in the planning domain or else comparisons between terms constructed from arithmetic operations applied to PNEs or real values.•Numeric Postcondition The numeric postcondition is a conjunction of additive as-signment propositions,NP p,the rvalues1of which are expressions that can be assumed to be of the form(*#t exp)where exp is#t-free.Definition3Plan A plan,for a planning instance with the ground action set A,is afinite set of pairs in Q>0×A(where Q>0denotes the set of all positive rationals).The pddl family of languages imposes a restrictive formalism for the representation of plans.In the temporal members of this family,pddl2.1(Fox&Long,2003),pddl2.2(Hoff-mann&Edelkamp,2005)and pddl+,plans are expressed as collections of time-stamped actions.Definition3makes this precise.Where actions are durative the plan also records the durations over which they must execute.Figure1shows an abstract example of a pddl+plan in which some of the actions arefixed-length durative actions(their dura-tions are shown in square brackets after each action name).Plans do not report events or processes.In these plans the time stamps are interpreted as the amount of time elapsed since the start of the plan,in whatever units have been used for modelling durations and time-dependent effects.Definition4Happening A happening is a time point at which one or more discrete changes occurs,including the activation or deactivation of one or more continuous processes. The term is used to denote the set of discrete changes associated with a single time point.1.Core Definition3defines rvalues to be the right-hand sides of assignment propositions.Fox&Long4.2Expressing Continuous ChangeIn pddl2.1the time-dependent effect of continuous change on a numeric variable is ex-pressed by means of intervals of durative activity.Continuous effects are represented by update expressions that refer to the special variable#t.This variable is a syntactic de-vice that marks the update as time-dependent.For example,consider the following two processes:(:process heatwater:parameters():precondition(and(<(temperature)100)(heating-on)):effect(increase(temperature)(*#t(heating-rate))))(:process superheat:parameters():precondition(and(<(temperature)100)(secondaryburner-on)):effect(increase(temperature)(*#t(additional-heating-rate))) )When these processes are both active(that is,when the water is heating and a secondary burner is applied and the water is not yet boiling)they lead to a combined effect equivalent to:d temperature=(heating-rate)+(additional-heating-rate)dtActions that have continuous update expressions in their effects represent an increased level of modelling power over that provided byfixed length,discrete,durative actions.In pddl+continuous update expressions are restricted to occur only in process effects. Actions and events,which are instantaneous,are restricted to the expression of discrete change.This introduces the three-part modelling of periods of continuous change:an action or event starts a period of continuous change on a numeric variable expressed by means of a process.An action or eventfinally stops the execution of that process and terminates its effect on the numeric variable.The goals of the plan might be achieved before an active process is stopped.Notwithstanding the limitations of durative actions,observed by Boddy(2003)and McDermott(2003a),for modelling continuous change,the durative action model can be convenient for capturing activities that endure over time but whose internal structure is irrelevant to the plan.This includes actions whosefixed duration might depend on the values of their parameters.For example,the continuous activities of riding a bicycle(whose duration might depend on the start and destination of the ride),cleaning a window and eating a meal might be conveniently modelled usingfixed-length durative actions.pddl+ does not force the modeller to represent change at a lower level of abstraction than is required for the adequate capture of the domain.When such activities need to be modelled fixed duration actions might suffice.The following durative action,again taken from the Planetary Lander Domain,illus-trates how durative actions can be used alongside processes and events when it is unnec-essary to expose the internal structure of the associated activity.In this case,the action models a preparation activity that represents pre-programmed behaviour.The constantsModelling Mixed Discrete-Continuous Domains for PlanningpartTime1and B-rate are defined in the initial state so the duration and schedule of effects within the specified interval of the behaviour are known in advance of the application of the prepareObs1action.(:durative-action prepareObs1:parameters():duration(=?duration(partTime1)):condition(and(at start(available unit))(over all(>(soc)(safelevel)))):effect(and(at start(not(available unit)))(at start(increase(demand)(B-rate)))(at end(available unit))(at end(decrease(demand)(B-rate)))(at end(readyForObs1))))4.3Planetary Lander ExampleWe now present an example of a pddl+domain description,illustrating how continuous functions,driven by interacting processes,events and actions,can constrain the structure of plans.The example is based on a simplified model of a solar-powered lander.The actions of the system are durative actions that draw afixed power throughout their operation. There are two observation actions,observe1and observe2,which observe the two different phenomena.The system must prepare for these,either by using a single long action, called fullPrepare,or by using two shorter actions,called prepareObs1and prepareObs2, each specific to one of the observation actions.The shorter actions both have higher power requirements over their execution than the single preparation action.The lander is required to execute both observation actions before a communication link is established(controlled by a timed initial literal),which sets a deadline on the activities.These activities are all carried out against a background offluctuating power supply. The lander is equipped with solar panels that generate electrical power.The generation process is governed by the position of the sun,so that at night there is no power generated, rising smoothly to a peak at midday and falling back to zero at dusk.The curve for power generation is shown in Figure2.Two key events affect the power generation:at nightfall the generation process ends and the lander enters night operational mode.In this mode it draws a constant power requirement for a heater used to protect its instruments,in addition to any requirements for instruments.At dawn the night operations end and generation restarts. Both of these events are triggered by a simple clock that is driven by the twin processes of power generation and night operations and reset by the events.The lander is equipped with a battery,allowing it to store electrical energy as charge. When the solar panels are producing more power than is required by the instruments of the lander,the excess is directed into recharging the battery(the charging process),while when the demand from instruments exceeds the solar power then the shortfall must be supplied from the battery(the discharging process).The charging process follows an inverse exponential function,since the rate of charging is proportional to the power devoted to charging and also proportional to the difference between the maximum and current levels of charge.Discharge occurs linearly at a rate determined by the current demands of all the lander activities.Since the solar generation process is itself a non-linear function of timeFox &Long 0 24681012141618200 2 4 6 810 12 14P o w e r (W a t t s )Time (hours after dawn)Figure 2:Graph of power generated by the solar panels.ChargingFigure 3:An abstracted example lander plan showing demand curve and supply curve overthe period of execution.during the day,the state of charge of the battery follows a complex curve with discontinuities in its rate of change caused by the instantaneous initiation or termination of the durative instrument actions.Figure 3shows an example of a plan and the demand curve it generates compared with the supply over the same period.Figures 5and 6show graphs of the battery state of charge for the two alternative plans shown in Figure 4.The plans both start an hour before dawn and the deadline is set to 10hours later.The parameters have been set to ensure that there are 15hours of daylight,so0.1:(fullPrepare)[5]5.2:(observe1)[2]7.3:(observe2)[2] 2.6:(prepareObs1)[2]4.7:(observe1)[2]6.8:(prepareObs2)[1]7.9:(observe2)[2]Figure 4:Two alternative plans to complete the observations before the deadline.the plan must complete within two hours after midday.The battery begins at 45%of fully charged.-Time 6Value0105.1daybreak d >s 099.519715fullPrepareobserve1observe2Figure 5:Graph of battery state of charge (as a percentage of full charge)for first plan.The timepoint marked d >s is the first point at which demand exceeds supply,so that the battery begins to recharge.The vertical lines mark the points at which processes are affected.Where the state of charge is falling over an interval the discharge process is active and where it is rising the charge process is active.The lander is subject to a critical constraint throughout its activities:the battery state of charge may never fall below a safety threshold.This is a typical requirement on remote systems to protect them from system failures and unexpected problems and it is intended to ensure that they will always have enough power to survive until human operators have had the opportunity to intervene.This threshold is marked in Figure 5,where it can be seen that the state of charge drops to approximately 20%.The lowest point in the graph is at a time 2.95hours after dawn,when the solar power generation just matches the instrument demand.At this point the discharging process ends and the generation process starts.This time point does not correspond to the start or end of any of the activities of the lander and is not a point explicitly selected by the planner.It is,instead,a point defined by the intersection of two continuous functions.In order to confirm satisfaction of the constraint,that the state of charge may never fall below its safety threshold,the state of charge must be monitored throughout the activity.It is not sufficient to consider its value at only its end points,where the state of charge is well above the minimum required,since the curve might dip well below these values in the middle.We will use this example to illustrate further points later in this paper.The complete do-main description and the initial state for this problem instance can be found in Appendix C,。

最最常用的关键词及音标数据类型：boolean、byte、short、int、long、double、char、float、double。

包引入和包声明：import、package。

用于类和接口的声明：class、extends、implements、interface。

流程控制：if、else、switch、do、while、case、break、continue、return、default、while、for。

异常处理：try、catch、finally、throw、throws。

修饰符：abstract、final、native、private、protected、public、static、synchronized、transient、volatile。

其他：new、instanceof、this、super、void、assert、const*、enum、goto*、strictfp。

Java基础常见英语词汇(共70个)['ɔbdʒekt] ['ɔ:rientid]导向的['prəʊɡræmɪŋ]编程OO: object-oriented ,面向对象OOP: object-oriented programming,面向对象编程[dɪ'veləpmənt][kɪt]工具箱['vɜːtjʊəl]虚拟的JDK:Java development kit, java开发工具包JVM:java virtual machine ,java虚拟机['dʒɑːvə] [mə'ʃiːn]机器[kəm'paɪl]Compile:编绎Run:运行['veərɪəb(ə)l] [ɒpə'reɪʃ(ə)n] [pə'ræmɪtə]variable:变量operation:操作,运算parameter:参数['fʌŋ(k)ʃ(ə)n]function:函数member-variable:成员变量member-function:成员函数[dɪ'fɔːlt] ['ækses] ['pækɪdʒ] [ɪm'pɔːt] ['stætɪk] default:默认access:访问package:包import:导入static:静态的[vɔid] ['peər(ə)nt] [beɪs] ['sjuːpə]void:无(返回类型) parent class:父类base class:基类super class:超类[tʃaɪld] [di'raivd] [əʊvə'raɪd] [əʊvə'ləʊd] child class:子类derived class:派生类override:重写,覆盖overload:重载['faɪn(ə)l] ['ɪmplɪm(ə)nts]final:最终的,不能改变的implements:实现[rʌn'taim] [æriθ'metik] [ik'sepʃən]Runtime:运行时ArithmeticException:算术异常[ə'rei] ['indeks] [baundz] [ik'sepʃən] [nʌl] ['pɔintə]指针ArrayIndexOutOfBoundsException:数组下标越界异常Null Pointer Exception:空引用异常ClassNotFoundException:类没有发现异常['nʌmbə]['fɔ:mæt]NumberFormatException:数字格式异常(字符串不能转化为数字)[θrəuz]Throws: (投掷)表示强制异常处理Throwable:(可抛出的)表示所有异常类的祖先类[læŋ] ['læŋɡwidʒ] [ju'til] [,dis'plei] [ə'rei] [list]Lang:language,语言Util:工具Display:显示 ArrayList:(数组列表)表示动态数组[hæʃ] [mæp]HashMap: 散列表,哈希表[swiŋ] ['æbstrækt] ['windəu] ['tu:lkit]Swing:轻巧的Awt:abstract window toolkit:抽象窗口工具包[freim] ['pænl] ['leiaut] [skrəul] ['və:tikəl] Frame:窗体Panel:面板Layout:布局Scroll:滚动Vertical:垂直['hɔri'zɔntəl] ['leibl] [tekst] ['fi:ld]Horizontal:水平Label:标签TextField:文本框['εəriə] ['bʌtən] [tʃek] [bɔks]TextArea:文本域Button:按钮Checkbox:复选框['reidiəu] ['kɔmbəu] ['lisənə]Radiobutton:单选按钮Combobox:复选框Listener:监听['bɔ:də] [fləu] [ɡrid] ['menju:] [bɑ:]Border:边界Flow:流Grid:网格MenuBar:菜单栏['menju:] ['aitəm] ['pɔpʌp]Menu:菜单MenuItem:菜单项PopupMenu:弹出菜单['daiəlɔɡ] ['mesidʒ] ['aikɔn] [nəud]Dialog:对话框Message:消息Icon:图标Node:节点['dʒa:və] ['deitəbeis] [,kɔnek'tivəti]Jdbc:java database connectivity ：java数据库连接[draivə] ['mænidʒə] [kə'nekʃən] ['steitmənt]DriverManager:驱动管理器 Connection:连接Statement:表示执行对象[pri'peəd] [ri'zʌlt]Preparedstatement:表示预执行对象Resultset:结果集['eksikju:t] ['kwiəri]executeQuery:执行查询334157810 这群每日java技术免费分享定期java资料更新Jbuilder中常用英文(共33个)[kləuz] [ik'sept] [peinz]Close all except…:除了..全部关闭Panes:面板组[bi:n] ['prɔpətiz] [meik] [bild] [,ri:'bild]Bean:豆子Properties:属性Make:编绎Build:编绎Rebuild:重编绎[ri'freʃ] ['prɔdʒekt] [di'fɔ:lt]Refresh:刷新Project properties:项目属性Default project properties:默认的项目属性[di:'bʌɡ] ['prefərənsiz] [kən'fiɡə] ['laibrəriz] Debug:调试Preferences:参数配置Configure:配置Libraries:库JSP中常用英文[,ju:ni'və:səl] [ri'sɔ:s] [ləu'keiʃən]URL: Universal Resource Location:统一资源定位符['intənet] [ik'splɔ:rə] ['dʒa:və] ['sə:və] [peidʒ]IE: Internet Explorer 因特网浏览器JSP: java server page：java服务器页面['mɔdəl] [kən'trəulə] ['tɔmkæt]Model:模型C:controller:控制器Tomcat:一种jsp的web服务器['mɔdju:l] ['sə:vlet] [i'niʃəlaiz] ['sta:tʌp] WebModule:web模块Servlet:小服务程序Init: initialize,初始化Startup:启动['mæpiŋ] [pə'ræmitə] ['seʃən] [,æpli'keiʃən]Mapping:映射Getparameter:获取参数Session:会话Application:应用程序['kɔntekst] [,ri:di'rekt] [dis'pætʃ] ['fɔ:wəd]Context:上下文redirect:重定向dispatch:分发forward:转交[ 'ætribju:t] ['kɔntent] [taip] setattribute:设置属性getattribute:获取属性contentType:内容类型[tʃɑ:] [in'klu:d] [tæɡ] [lib]charset:字符集include:包含tag:标签taglib:标签库[ik'spreʃən] ['læŋɡwidʒ] [skəup] ['empti]EL:expression language,表达式语言Scope:作用域Empty:空['stændəd] [tæɡ] ['laibrəri]JSTL:java standard tag library ：java标准标签库[di'skripʃən] [kɔ:]TLD:taglib description,标签库描述符Core:核心Foreach:表示循环[va:(r)] ['vεəriəbl] ['steitəs] ['aitəm]Var:variable,变量Status:状态Items:项目集合['fɔ:mæt] [filtə]Fmt:format,格式化Filter:过滤器334157810 这群每日java技术免费分享定期java资料更新(报错英文['strʌktʃəz]Data Structures 基本数据结构['dikʃənəriz]Dictionaries 字典[prai'ɔrəti] [kju:z]Priority Queues 堆[ɡrɑ:f] ['deɪtə] ['strʌktʃəz]Graph Data Structures 图[set] ['deɪtə]['strʌktʃəz]Set Data Structures 集合[tri:s]Kd-Trees 线段树[nju:'merikəl] ['prɔ:bləms]Numerical Problems 数值问题[sɔlviŋ] ['liniə] [i'kweiʃənz]Solving Linear Equations 线性方程组['bændwidθ] [ri'dʌkʃən]Bandwidth Reduction 带宽压缩['meitriks] [,mʌltipli'keiʃən]Matrix Multiplication 矩阵乘法[di'tə:minənt] ['pə:mənənt]Determinants and Permanents 行列式[kən'streind] [ʌnkən'streɪnd] [,ɔptimai'zeiʃən] Constrained and Unconstrained Optimization 最值问题['liniə] ['prəuɡræmiŋ]Linear Programming 线性规划['rændəm] ['nʌmbə] [,dʒenə'reiʃən]Random Number Generation 随机数生成['fæktərɪŋ] [prai'mæləti] ['testɪŋ]Factoring and Primality Testing 因子分解/质数判定['ɑːbɪtrərɪ][prɪ'sɪʒən][ə'rɪθmətɪk]Arbitrary Precision Arithmetic 高精度计算['næpsæk] ['prɒbləm]Knapsack Problem 背包问题[dɪ'skriːt] ['fʊriər] [træns'fɔːm]Discrete Fourier Transform 离散Fourier变换Combinatorial Problems 组合问题Median and Selection 中位数Generating Permutations 排列生成Generating Subsets 子集生成Generating Partitions 划分生成Generating Graphs 图的生成Calendrical Calculations 日期Job Scheduling 工程安排Satisfiability 可满足性Graph Problems -- polynomial 图论-多项式算法Connected Components 连通分支Topological Sorting 拓扑排序Minimum Spanning Tree 最小生成树Shortest Path 最短路径Transitive Closure and Reduction 传递闭包Matching 匹配Eulerian Cycle / Chinese Postman Euler回路/中国邮路Edge and Vertex Connectivity 割边/割点Network Flow 网络流Drawing Graphs Nicely 图的描绘Drawing Trees 树的描绘Planarity Detection and Embedding 平面性检测和嵌入Graph Problems -- hard 图论-NP问题Clique 最大团Independent Set 独立集Vertex Cover 点覆盖Traveling Salesman Problem 旅行商问题Hamiltonian Cycle Hamilton回路Graph Partition 图的划分Vertex Coloring 点染色Edge Coloring 边染色Graph Isomorphism 同构Steiner Tree Steiner树Feedback Edge/Vertex Set 最大无环子图Computational Geometry 计算几何Convex Hull 凸包Triangulation 三角剖分Voronoi Diagrams Voronoi图Nearest Neighbor Search 最近点对查询Range Search 范围查询Point Location 位置查询Intersection Detection 碰撞测试Bin Packing 装箱问题Medial-Axis Transformation 中轴变换Polygon Partitioning 多边形分割Simplifying Polygons 多边形化简Shape Similarity 相似多边形Motion Planning 运动规划Maintaining Line Arrangements 平面分割Minkowski Sum Minkowski和Set and String Problems 集合与串的问题Set Cover 集合覆盖Set Packing 集合配置String Matching 模式匹配Approximate String Matching 模糊匹配Text Compression 压缩Cryptography 密码Finite State Machine Minimization 有穷自动机简化Longest Common Substring 最长公共子串Shortest Common Superstring 最短公共父串DP——Dynamic Programming——动态规划recursion ——递归)报错英文第一章：JDK(Java Development Kit) java开发工具包JVM(Java Virtual Machine) java虚拟机Javac 编译命令java 解释命令Javadoc 生成java文档命令classpath 类路径Version 版本static 静态的String 字符串类334157810 这群每日java技术免费分享定期java资料更新JIT(just-in-time) 及时处理：第三章：OOP object oriented programming 面向对象编程Object 对象Class 类Class member 类成员Class method 类方法Class variable 类变量Constructor 构造方法Package 包Import package 导入包第四章：Base class 基类Super class 超类Overloaded method 重载方法Overridden method 重写方法Public 公有Private 私有Protected 保护Static 静态Abstract 抽象Interface 接口Implements interface 实现接口第五章：RuntimeExcepiton 运行时异常ArithmeticException 算术异常IllegalArgumentException 非法数据异常ArrayIndexOutOfBoundsException 数组索引越界异常NullPointerException 空指针异常ClassNotFoundException 类无法加载异常（类不能找到）NumberFormatException 字符串到float类型转换异常（数字格式异常）IOException 输入输出异常FileNotFoundException 找不到文件异常EOFException 文件结束异常InterruptedException （线程）中断异常throws 投、掷、抛print Stack Trace() 打印堆栈信息get Message（）获得错误消息get Cause（）获得异常原因method 方法able 能够instance 实例Byte （字节类）Character （字符类）Integer（整型类）Long （长整型类）Float（浮点型类）Double （双精度类）Boolean（布尔类）Short （短整型类）Digit （数字）Letter （字母）Lower (小写)Upper (大写)Space (空格)Identifier (标识符)Start (开始)String (字符串)length （值）equals (等于)Ignore （忽略）compare （比较）sub （提取）concat （连接）trim （整理）Buffer (缓冲器)reverse (颠倒)delete （删除）append （添加）Interrupted （中断的）第七章：toString 转换为字符串GetInstance 获得实例Util 工具，龙套Components 成分，组成Next Int 下一个整数Gaussian 高斯ArrayList 对列LinkedList 链表Hash 无用信息，杂乱信号Map 地图Vector 向量，矢量Collection 收集Shuffle 混乱，洗牌RemoveFirst 移动至开头RemoveLast 移动至最后lastElement 最后的元素Capacity 容量，生产量Contains 包含，容纳InsertElementAt 插入元素在某一位置334157810 这群每日java技术免费分享定期java资料更新第八章：io->in out 输入/输出File 文件isFile 是文件isDirectory 是目录getPath 获取路径getAbsolutePath 获取绝对路径lastModified 最后修改日期Unicode 统一的字符编码标准, 采用双字节对字符进行编码FileInputStream 文件输入流FileOutputStream文件输出流IOException 输入输出异常fileobject 文件对象available 可获取的BufferedReader 缓冲区读取FileReader 文本文件读取BufferedWriter 缓冲区输出FileWriter 文本文件写出flush 清空close 关闭DataInputStream 二进制文件读取DataOutputStream二进制文件写出EOF 最后encoding 编码Remote 远程release 释放第九章：JBuider Java 集成开发环境（IDE）Enterprise 企业版Developer 开发版Foundation 基础版Messages 消息格Structure 结构窗格Project 工程Files 文件Source 源代码Design 设计History 历史Doc 文档File 文件Edit 编辑Search 查找Refactor 要素View 视图Run 运行Tools 工具Window 窗口Help 帮助Vector 矢量addElement 添加内容Project Winzard 工程向导Step 步骤Title 标题Description 描述Copyright 版权Company 公司Aptech Limited Aptech有限公司author 作者Back 后退Finish 完成version 版本Debug 调试New 新建ErrorInsight 调试第十章：JFrame 窗口框架JPanel 面板JScrollPane 滚动面板title 标题Dimension 尺寸Component 组件Swing JAVA轻量级组件getContentPane 得到内容面板LayoutManager 布局管理器setVerticalScrollBarPolicy 设置垂直滚动条策略AWT（Abstract Window Toolkit）抽象窗口工具包GUI （Graphical User Interface）图形用户界面VERTICAL_SCROLLEARAS_NEEDED 当内容大大面板出现滚动条VERTICAL_SOROLLEARAS_ALWAYS 显示滚动条VERTICAL_SOROLLEARAS_NEVER 不显示滚动条JLabel 标签Icon 图标image 图象LEFT 左对齐RIGHT 右对齐JTextField 单行文本getColumns 得到列数setLayout 设置布局BorderLayout 边框布局CENTER 居中对齐JTextArea 多行文本setFont 设置字体setHorizontalAlignment 设置文本水平对齐方式setDefaultCloseOperation 设置默认的关闭操作add 增加JButton 按钮JCheckBox 复选框JRadioButton单选按钮addItem 增加列表项getItemAt 得到位置的列表项getItemCount 得到列表项个数setRolloverIcon 当鼠标经过的图标setSelectedIcon 当选择按钮的图标getSelectedItem 得到选择的列表项getSelectedIndex 得到选择的索引ActionListener 按钮监听ActionEvent 按钮事件actionPerformed 按钮单击方法(编程词汇A2A integration A2A整合abstract 抽象的abstract base class (ABC)抽象基类abstract class 抽象类abstraction 抽象、抽象物、抽象性access 存取、访问access level访问级别access function 访问函数account 账户action 动作activate 激活active 活动的actual parameter 实参adapter 适配器add-in 插件address 地址address space 地址空间address-of operator 取地址操作符ADL (argument-dependent lookup)ADO(ActiveX Data Object)ActiveX数据对象advanced 高级的aggregation 聚合、聚集algorithm 算法alias 别名align 排列、对齐allocate 分配、配置allocator分配器、配置器angle bracket 尖括号annotation 注解、评注API (Application Programming Interface) 应用(程序)编程接口app domain (application domain)应用域application 应用、应用程序application framework 应用程序框架appearance 外观append 附加architecture 架构、体系结构archive file 归档文件、存档文件argument引数(传给函式的值)。

a rXiv:g r-qc/6118v 114Nov26A new proposal for group field theory I:the 3d case James Ryan ∗Department of Applied Mathematics and Theoretical Physics,Centre for Mathematical Sciences,Wilberforce Road,Cambridge CB30WA,UK (Dated:February 6,2008)Abstract In this series of papers,we propose a new rendition of 3d and 4d state sum models based upon the group field theory (GFT)approach to non-perturbative quantum gravity.We will see that the group field theories investigated in the literature to date are,when judged from the position of quantum field theory,an unusual manifestation of quantum dynamics.They are one in which the Hadamard function for the field theory propagates a-causally the physical degrees of freedom of quantum gravity.This is fine if we wish to define a scalar product on the physical state space,but it is not what we generally think of as originating directly from a field theory.We propose a model in 3d more in line with standard quantum field theory,and therefore the field theory precipitates causal dynamics.Thereafter,we couple the model to point matter,and extract from the GFT the effective non-commutative field theory describing the matter dynamics on a quantum gravity background.We identify the symmetries of our new model and clarify their meaning in the GFT setting.We are aided in this process by identifying the category theory foundations of this GFT which,moreover,propel us towards a categorified version for the 4d case.I.INTRODUCTIONCurrently,spin foam models[1,2]draw considerable interest as a general formalism for quantum gravity.The reasons are multifarious.For instance,they occur at a point of convergence of different objectives,including loop quantum gravity[3,4],topologicalfield theories[5],and simplicial gravity.Indeed,the spin foam picture emerges when considering the evolution in time of spin networks-kinematical states of quantum general relativity(ensuing from loop quantum gravity).As we said,it arises in the development of topologicalfield theories including3d gravity. In these models,category theory plays a major role,since their whole construction can be rephrased in terms of operations in the category of Lie groups.On a different tack,spin foams naturally arise as lattice discretizations of the path integral for gravity and generally covariant gauge theories.Moreover,they provide a background independent discrete quantum gravity path integral, by representing space-time as a combinatorial cellular complex upon which we encode geometric data in a purely group-theoretic and algebraic manner.This encoding may be done in two equivalent ways:in the‘configuration-space’representation where the geometry labels for the cellular2-complex are Lorentz group representations;or alternatively,in the‘momentum-space’representation where the labels occur as Lorentz group elements.A colouring consistent with a choice of geometry is an admissible configuration,and once this has been completed,we proceed to assign it a quantum amplitude.The discretization reduces the number of degrees of freedom tofinitely many,thus enabling the definition of a functional measure.This makes the formulation seem similar to standard lattice gauge theory.But although the manner of the truncations are akin to each other,its nature in the quantum gravity setting is intrinsically different to that of conventional lattice theory.As expected,background independence tells us that we cannot consider the cellular complex as a UV regulator.Summing over admissible configurations weighted by their chosen quantum amplitude gives us our partition function.The cell complex is usually chosen to be topologically dual to a simplicial complex of the appropriate dimension.In turn,spin foam models have been obtained from so-called groupfield theories[6,7].A groupfield theory(GFT), as its name suggests,is afield theory over a group manifold,which generates a sum over all cellular2-complexes in its Feynman diagram expansion.An equivalent way of expressing this result is to say that we obtain a sum over all coloured simplicial complexes,by the duality mentioned above,and thus a sum over all geometries and topologies, of a given dimension.The impact of such a formalism is two-fold.Unlike gravity in3d,the4-dimensional theory is not a topologicalfield theory and thus contains more than just global degrees of freedom.Indeed,we can read in any number of expositions about the infinite set of local degrees of freedom inherent in any theory based on4d gravity.Thus,inserting afixed,albeit coloured,discrete structure such as a cellular complex,destroys the background independence of our resultant quantum theory.But this can be restored by a summation over geometries,that is, a summation over all simplicial complexes discretizing a given manifold M.The groupfield theory provides a well defined prescription for implementing this sum.But it goes further,in that there is a sum over manifolds M in the GFT,thus realizing a dream of many relativists to make yet another of the fundamental structures of nature dynamical,the space-time topology.The quantum dynamics of the GFT can be viewed as a‘local simplicial third quantization’of gravity1.To explicate this point more thoroughly,the GFTfiled represents a fundamental building block of space,a(d−1)dimensional ball.A collection offields comprises a quantum a state of geometry.Thus,the GFT path integral describes the quantum dynamics of this quantum state.The classical equations of motion related to this GFT embody the Hamiltonian constraint for gravity,infiled theory language.Thus,solutions to the classical equations of motion are quantum states of geometry which are solutions to the Hamiltonian constraint.In other words,solutions are elements of the physical state space of loop quantum gravity.This is in analogy with matter field theory,where the2nd quantized Klein-Gordonfield represents a quantum state of geometry.The path integral then represents its quantum dynamics.The classical Klein-Gordonfield then represents solutions to the Hamiltonian constraint for the particle,where the momentum is on-shell;and thus represents a state in the physical space of the 1st quantized theory.In4-dimensions,there exist promising and recently much studied spin foam models,and groupfield theories,with many interesting features and issues still in need of clarification.On the other hand in3d,where gravity is a topological field theory,we have a much more complete story.We know that its quantization derived using spin foam models is equivalent to those obtained by other approaches,such as loop quantum gravity[8],Chern-Simons quantization,’t Hooft’s polygon approach[9]etc.Furthermore,3d gravity raises many of the issues involved in the quantization of gravity such as:the conceptual problem of time,the problem of the construction of physically relevant observables,the emergence of the semiclassical space-time geometry,the effect of a cosmological constant,the quantum causal nature,the role of diffeomorphisms;the sum over topologies etc.Thus,3d gravity provides an excellent testing ground for theories of quantum gravity.The coupling of matterfields to quantum gravity in the spin foam framework is of major importance.Matter coupling might provide the best,if not the only,way to attack certain issues that are notoriously difficult in a pure gravity theory.They provide an avenue to define quantum gravity observables that have a clear physical meaning. Furthermore,they stimulate a program of quantum gravity analysis,supplementing the hypothesis that quantum gravity affects the usual predictions of quantumfield theory.Over and above this,quantum gravity might hopefully solve problems in quantumfield theory.For example,quantumfield theories are in general plagued by ultraviolet divergences,but quantum gravity might provide a built-in covariant cut-offat the Planck scale.Recently this agenda has received much attention.In[10],point matter was coupled to gravity from the canonical perspective.The resulting quantum dynamics are played out on a simplicial manifold of topologyΣ×R(Σis a Riemann surface),a particular subspecies of spin foams.The path integral formulation has concurrently made similar progress[11,12].The covariant discretization generalizes the canonical results in the sense that one may deal with afixed manifold of arbitrary topology.Work within the covariant formalism oiled the wheels of progress towards a phenomenological understanding of matter in the quantum gravity setting.By summing over the gravity degrees of freedom,the matter spin foam theory takes on the character of a Feynman diagram of a non-commutative field theory[13,15].The momentum space realization of this theory has support on the group SU(2),rather than the corresponding Lie algebra su(2)∼R3,and thus has bounded momentum.Hence we are dealing with another incarnation of groupfield theory.Since this effectivefield theory encodes the sum total of the quantum gravity effects in the matter sector,we should be able to extricate the gravity degrees of freedom and embellish the effective theory so that it may be written as a groupfield theory in the spin foam sense[16,17].Another facet of discrete quantum gravity currently the subject of much research is the imposition of causal restrictions[18,19].When we pen any path integral formulation,we have several alternatives,depending on our motivation[20].One option is to use the sum-over-histories to project the kinematical states down onto their physical subspace,and provide us with a physical inner product.This amplitude is real,it does not attribute an incoming or outgoing status to the states.Thus it tenders an a-causal dynamics.Another choice within the path integral furnishes us with causal dynamics.Adhering to a covariant prescription implies blindness towards time-ordering.Knowledge of space-time orientation,however,is enough to impose a causal structure[21].This has already been extended to the groupfield theory.These‘generalized groupfield theories’[22]register space-time orientation in their operators, utilizing a mechanism reminiscent of Feynman’s proper time formalism.This article shall be devoted to the proposal and study of a new GFT approach.The motivation for this proposal is that when we contemplate groupfield theory we get caught in the following dilemma.On the one hand,we rely on an analogy with quantumfield theory to justify our belief in groupfield theory as the fundamental theory.The other hand,unfortunately,has something in store for us.The majority of GFTs to date do not include causality,which does not coincide with conventional quantumfield theory.In the standard QFT setting,the kinetic operator inverts to become the Feynman propagator and hence labels causal amplitudes.The corresponding a-causal dynamics are accommodated by the Hadamard function,a non-invertible operator on the space offields.Generalized GFTs remedy this situation,with causal dynamical operators occurring in both the kinetic and vertex operators.They provide,at the moment,the most fundamental implementation of causality in discrete quantum gravity.They register a specific record of the orientation of the simplicial building blocks,for both space and space-time,and this is shown to generate orientation dependent spin foam quantum amplitudes.In[19],causality is included in a superficially different fashion. The explicit orientation labels are obscured,but the quantum amplitude registers orientation dependence.This suggests that we might be able to include causality in a more direct,albeit possibly less fundamental fashion in the GFT.Moreover,since the a-causal dynamics of earlier GFTs are included in the vertex term,the matter coupling in [16,17]is also included completely in the vertex term.The generalized GFTs corresponding to these theories will again provide an implementation of causality in terms of explicit orientation dependence of the simplices.Of course, since this dependence is included into the kinetic as well as vertex terms,it provides an avenue to transfer vital matter information from the vertex to kinetic term.We require this if the generalized GFTs are to reduce to the effective field theory for matter.But we are again motivated by these complications to opt for a direct manner of including causal matter and causal gravity information in the GFT kinetic term.Our proposal alleviates these difficulties by directly placing a causal dynamical operator in the kinetic term of the GFT.This further facilitates its subsequent reduction to the correct matter effectivefield theory.While symmetries in GFT are notoriously difficult to elucidate,our new formalism clarifies their position in the action,with respect to their position at the level of the spin foam amplitudes.Spin foam models have a categorical description in terms of morphisms,natural transformations,functors etc.We make this identification explicit in the GFT locale and briefly mention further work in4d.Finally,an important step in making this new GFT a reality required a fundamental shift in how we regard the various discrete structures arising in our quantization of gravity.We do not directly deal with a simplicial complex as a discretization of our manifold.Instead we deal with the more general CW-complex.But from the GFT context we cannot generate an arbitrary cell-complex,so we refine our choice.We discretize our manifold using a cell-complex whose dual structure is a simplicial complex.To emphasize our point,the spin foam2-skeleton is now a simplicial complex.So the spin foam amplitudes are not in general Ponzano-Regge amplitudes,but are an equally valid state-sum for3d gravity.In the next section,we introduce the formal aspects of the path integral quantization of gravity.We exploit an analogy with the2nd quantization of point particle theory,to illuminate what we demand of our GFT.In section III, we provide an elementary description of the Ponzano-Regge model for3d quantum gravity,along with its incorporation of matter and causality,especially with regard to the effectivefield theory for matter.Following that,we describe the creation of these amplitudes as the Feynman diagrams of groupfield theories,again with a concise account of how they incorporate matter features.In section IV,we will begin with a precise rendition of how our new viewpoint with respect to the discrete space-time structures,before proceeding onto its embodiment as a groupfield theory.We thereafter develop our model to include matter,and reduce it to the effectivefield theory.After analyzing the model’s symmetries,wefinish our exposition with some concluding statements in section V.II.THE PATH INTEGRAL QUANTIZATION FOR QUANTUM GRA VITYAn elegant analysis of this topic occurs in[18],so let us be brief.There is a formal analogy between the covariant 1st and2nd quantizations of point particle matter and those of gravity.Here,we shall only outline the gravity case.A.Quantum gravityWe define,formally,the path integral approach to quantum gravity where the transition amplitude is a sum over all4-geometries interpolating between given boundary3-geometries.This sum is weighted by the exponential of (i times)the Einstein Hilbert action for general relativity and a suitable measure on the space of(diffeomorphism classes of)4-metrics.Furthermore,there is a possible additional sum over all the possible manifolds,i.e topologies, having the given boundary2.The action can be re-expressed in its Hamiltonian formulation for manifolds of topology M∼Σ×R.Once we transplant to this context,we will see more clearly how explicit traces of causality appear.S M(h,π,N i,N)= M d3x dt(πij h ij−N H−N i H i),(1)where the variables are h ij,the3-metric induced on a spacelike slice of the manifold M,πij is its conjugate momentum, the shift N i,a Lagrange multiplier that enforces the spatial diffeomorphism constraint H i=0,and the lapse N that enforces the Hamiltonian constraint H=0.The Hamiltonian constraint encodes the dynamics of the theory and the symmetry under time diffeomorphisms3.We neglect to describe more about the former constraint.We will be more interested in the integration over the lapse where our choice of range for this variable is crucial.If we choose the range(−∞,∞),then we have projected onto the physical state space of quantum gravityh1|h2 phys= +∞−∞D N g|h1,h2 x D g ij(x)Dπij(x) e i S.(2) physBut this expression is completely invariant under the reversal of space-time orientation.The reason for this is that the canonical algebra generated by H i and H induces a larger symmetry than4-diffeomorphism invariance.What is more,like its counterpart in matterfield theory,(2)is the Hadamard function for gravityG H(h1,h2)=phys h2|h1 phys=kin h2|“δ(H)”|h1 kin(3)Formally,this is a solution of the Wheeler-DeWitt equation in both arguments and does not register any notion of whether a state is incoming or outgoing.If we want to include causality we must restrict the range of the lapse to (0,+∞).This gives us the quantity analogous to the Feynman propagatorG F(h1,h2)= +∞0D N g|h1,h2 x D g ij(x)Dπij(x) e i S= h2|h1 C=kin h2|“1this theory can be summed up by a BF-theory action.The basic variables in the classical theory are:an su(2)-valued triad framefield E=E iµJ i dxµ;and an su(2)-valued spin connectionfield,A=A iµJ i dxµ.4From these fundamental fields we can construct other familiar quantities:the metric gµν=E iµE jµδij,the curvature F(A)=dA+A∧A,the torsion d A E=dE+[A,E].Most importantly,we can now write down the1st order action for3d gravity which encodes the dynamical information of the theory5:1S M[E,A]=4J i(i=0,1,2)are the generators of an su(2)algebra satisfying tr(J i J j)=2δij and[J i,J j]=2iǫijk J k.Furthermore,theµ=0,1,2 are space-time indices.5κ=4πG N where G N is Newton’s constant in3d.We shall choose units so thatκ=1.6By specifying an intertwiner,we are in effect decomposing the higher valent vertex into a product of3-valent intertwiners.C.Imposing the curvature constraintThere are now two possible paths down which we could continue our investigation of3d quantum gravity:canonical and covariant.Since we are more interested in the covariant way,we shall concentrate on that approach.The partition function for3d gravity is given formally by:Z GR= D A D E e i S M[E,A]=“ D Aδ(F(A))”(12)We can make this formula rigorous by regularizing the path integral.In the Ponzano-Regge model one regularizes using a simplicial lattice and replaces the variables by discrete analogues.The manifold M is replaced by a simplicial counterpart∆,which has tetrahedra t,faces f,edges e and vertices v.The dual2-skeleton∆∗,is an important structure for our regularization.It is defined as the set of vertices v∗(∼t),edges e∗(∼f)and faces f∗(∼e)7.In the case of a manifold with boundary∂M,the intersection of∆∗with the boundary gives the boundary triangulation, and likewise the intersection of∆∗with the boundary gives the dual graph on the boundary.We denote these by∂∆and∂∆∗respectively.The continuousfields are replaced as follows:E→ e E=X e∈su(2),(13)A→ e∗A=g e∗∈SU(2),(14)F(A)→ e∗⊂∂f∗gǫf∗(e∗)e∗=G e∈SU(2).(15)whereǫf∗(e∗)=±1is the the relative orientation of the edge e∗and the face f∗.Thus the partition function assumes the form:Z P R= e∗ SU(2)dg e∗ e su(2)dX e e i P e tr(X e G e)= e∗ SU(2)dg e∗ eδ(G e)= e j e e d j e t j1j2j3j4j5j6 t,(16)after Plancherel decomposition of theδ-functions8.In this way,we introduce the su(2)representations to each face f∗and an intertwiner to each edge e∗(∼f).For four faces f forming a tetrahedron t,these intertwiners combine to form a6j-symbol.To see the boundary states arising naturally from the spin foam,we consider its intersection with a boundary and the subsequent labeling of the discrete structures∂∆∗and∂∆.A boundary edge¯e∗inherits the representation of the incident bulk face f∗while a boundary vertex¯v∗inherits the intertwiner from the incident bulk edge e∗.Thus, in the covariant formalism,the boundary states are given by spin-networks.This is comforting as we want the spin foam to impose the curvature constraint.D.Covariant symmetries and Gauge-fixingThe Ponzano-Regge amplitude is only a formal topological invariant.The amplitude is divergent due to the infinite sum over representation value.It may be regularized by introducing a cutoff.This can be done rigorously by deforming the algebra from SU(2)to U q(SU(2))where q is some root of unit and is the cut-offparameter.This gives rise to the2whereǫ(g)=sign(cosθ)and g=cosθ+i σ· n sinθ.We donot include this factor forsimplicity.well-known Turaev-Viro model[5],an exact topological state sum which has been related to3d quantum gravity with cosmological constant.There is a reason for the divergence in the amplitude which is more intrinsic to the theory from which it originated. It appeals directly to our experience regarding gauge theory in general,i.e.the presence of gauge symmetries results in divergences in the path integral.We should only integrate over gauge equivalence classes to get a sensible amplitude; this is done by gauge-fixing.The continuum action has two symmetries:Lorentz and translation,and although replacing the continuum manifold with a simplicial one destroys much of these symmetries,there is a residual action of each on the discrete manifold[11,25].To ensure afinite amplitude,we shall use up the gauge freedom tofix elements of the amplitude to desired values. For a systematic implementation of this procedure,we utilize two structures,a maximal tree T of edges in∆and a maximal tree T∗of edges in∆∗.An exhaustive explanation of the subsequent procedure is given in[26],but we can sum up the end result by saying that the gauge symmetry is used up to set every representation j e attached to e∈T to zero and every holonomy g e∗attached to e∗∈T∗to the identity.Gauge-fixing in such a manner gives rise to a Fadeev-Popov determinant which turns out in this case to be equal to1.Furthermore,the gauge-fixed amplitude turns out to be independent of the maximal trees T,T∗chosen.In the presence of boundaries the maximal tree T∗extends to edges¯e∗of the graph∂∆∗,but the tree T does not.In fact T can have at most one vertex on the boundary. The reason is that there is no translation symmetry on the boundary(φ=0on∂M).For the Riemannian case that we have been dealing with the redundant Lorentz integration has nothing to do with the divergences as the SU(2)group is compact and has a normalized Haar measure9.All the divergence is locked up in the redundant integration over the su(2)-algebra variables X e,e∈T.At the level of the amplitude this amounts to inserting a gauge-fixing observable[11]into the partition function(16)O T(j e)= e∈Tδj e,0.(17)Now this observable seems to destroy theflatness condition for the holonomy associated to edges in the maximal tree. This redundancy of a maximal tree ofδ-functions may be seen directly at the level of the spin-foam amplitude.The discrete Bianchi identity takes the forme:v⊂∂e g−1v∗(e)Gǫv(e)e g v∗(e)=1,(18)withǫv(e)=±1records the orientation of the edge e with respect to the vertex v,and g v∗(e)is a specific product of group elements g e∗.To explain this relationship in words,consider a vertex v∈∆and all the edges e incident at v.The Bianchi identity states that there exists an ordering of the edges e such that the product of their associated holonomies(up to conjugation)is the identity element.Now consider the non-gauge-fixed amplitude(16)10.This forces the curvature to be zero on all edges e.But for a vertex with n incident edges,once n−1are forced to be the identity,the Bianchi identity assures us that thefinal edge has zero curvature.This means that we have a redundant δ-function.This argument extends to a maximal tree.E.Inclusion of matterA recent advance in the spin foam formalism has been the inclusion of point particles in the Ponzano-Regge model [11,12,13].The coupling of matterfields is obtained as anticipated,by treating a full Feynman graphγof a particle field theory(of arbitrary spin),with its hidden dependence on geometric variables,as a quantum gravity observable. The coupling between geometric and matter degrees of freedom at each line of propagation of the graph is obtained by a discretization of the continuum action describing the coupling of gravity to relativistic point particles in3d,with the line of the Feynman graph thus being interpreted as the trajectory of a relativistic particle in a3d space-time, and by the subsequent integration over particle data.One considers a particle graphγembedded into the space-time manifold M.The dynamical information associated to this configuration is the minimal coupling of classical relativistic point particles to gravity.The action is given explicitly by:1S M,γ=9Such is not the case in the Lorentzian scenario where the gauge group is SU(1,1)(or SO(2,1))which is non-compact.10We refer the reader to Appendix A.The action maintains the same symmetries as in pure gravity as long as u →k −1u,q →k −1qk under Lorentz transformations and u →u,q →q +φunder translations.The equations of motion are:E :F (A )=pδγp =m uJ 0u −1,A :d A E =jδγj =s uJ 0u −1−m [uJ 0u −1,q ],where δγis the δ-function with support on the worldline.The first two equations of motion report that the curvature and torsion are zero except on the worldline of the particle,where they are proportional to the momentum and angular momentum respectively.The path integral is thenZ M ,γ= D A D E D q D p e i S M ,γ.(20)Once again we provide a simplicial discretization of the manifold M with certain edges adapted to the Feynman graph γ,denoted by ∆and Γrespectively.Upon this structure,we replace the continuum geometric data as before with its discrete counterpart.Here,we shall also do the same for the matter degrees of freedom which propagate along the worldline.Remember,we had five components to describe the particle:mass,spin,vector in the Cartan subalgebra,momentum and position (or alternatively:total angular momentum).To this end,every edge e ∈Γin the particle graph is labeled by a deficit angle m e ,and a spin s e .The vector in the Cartan subalgebra is contain in a group element h m e 11.Furthermore,the momentum of the particle is summed up in a variable u e ∈SU(2)colouring each edge 12.To the endpoints of each edge e ∈Γ,we assign total angular momentum variables,I s (e ),I t (e ),where s (e )and t (e )are the source and target vertices respectively.These total angular momenta are representations of SU(2).Thus-far,we have labeled the triangulation and its dual with the fundamental constituents.We construct the quantum amplitude out of these quantities.For an edge e /∈Γ,we impose flatness of the holonomy:δ(G e ).This is the usual case for pure gravity.For an edge e ∈Γ,we force the curvature to be in the conjugacy class of θe :δ(G e u e h m e u −1e ),where h m e ∈U(1).This imposes the expected curvature deformation coming from the particle.For an edge e ∈Γ,we also attach a spin projector:∆I t(e )I s (e )s e (u e )l t (e )l s (e )=D I t (e )l t (e )s e (u e )D I s (e )s e l s (e )(u e )−1.(21)To every vertex v ∈Γ,we associate an invariant tensor C I s (e )...l s (e )...intertwining the total angular momentum variables coming from each edge e incident there.For the group SU(2)these intertwiners are the Clebsch-Gordan coefficients.First we summarize the kinematical properties of the theory.A boundary state is defined on an open spin-network graph.This has edges joining trivalent vertices,and edges joining a 4-valent vertex to the point where the particle punctures the boundary.To the first type of edge we assign the holonomy of the connection in a given representation of SU(2).To the second type of edge we allocate the holonomy of the connection in a given representation of SU(2)projected down onto the spin-s component:D j ¯e ∗.s (x ¯e ∗),.We label the vertices with intertwiners.The amplitude is well defined once we chose a gauge-fixing.In order to do so we choose T a maximal tree of ∆/Γand T ∗a maximal tree of ∆∗and fix there as prescribed in [11].Thus the particle amplitude may be written:Z ∆,Γ= e ∗/∈T ∗dg e ∗ e/∈T ∪Γδ(G e ) e ∈Γ∆(m e ) du e δ(G e u e h m e u −1e )D I t (e )·l t (e )(a e)∆I t (e )I s (e )s e (u e )l t (e )l s (e ) v ∈ΓC I s (e )...l s (e )...,(22)where ∆(m e )=sin m e and D (a e )is a function of holonomies multiplying the spin projector.Its origin is in the occurrence of the Bianchi identity when searching for momentum conservation at the vertices of Γ.Remember that the Bianchi holds,up to conjugation of the holonomies.Therefore,momentum is conserved up to conjugation and we need these elements in the spin projector to have a consistently defined amplitude.We can reformulate this amplitude so as to make it more amenable to a field theory description.There are two ways of thinking about this procedure:either as summing over gravity degrees of freedom so as to end up with an effective amplitude for the particle degrees of freedom;or as using the the topological nature of the state sum for pure quantum gravity in 3d to re-express the amplitude on the simplest possible discretization encoding the particles’degrees of freedom.The simplest such diagram is such that the edges of Γonly,are the edges of the discretization.。