下载文档原格式
数学专业英语词汇(N)n ary relation n元关系n ball n维球n cell n维胞腔n chromatic graph n色图n coboundary n上边缘n cocycle n上循环n connected space n连通空间n dimensional column vector n维列向量n dimensional euclidean space n维欧几里得空间n dimensional rectangular parallelepiped n维长方体n dimensional row vector n维行向量n dimensional simplex n单形n dimensional skeleton n维骨架n disk n维圆盘n element set n元集n fold extension n重扩张n gon n角n graph n图n homogeneous variety n齐次簇n person game n人对策n simplex n单形n sphere bundle n球丛n th member 第n项n th partial quotient 第n偏商n th power operation n次幂运算n th root n次根n th term 第n项n times continuously differentiable n次连续可微的n times continuously differentiable function n次连续可微函数n tuple n组n tuply connected domain n重连通域n universal bundle n通用丛nabla 倒三角算子nabla calculation 倒三角算子计算nabla operator 倒三角算子napier's logarithm 讷代对数natural boundary 自然边界natural boundary condition 自然边界条件natural coordinates 自然坐标natural equation 自然方程natural equivalence 自然等价natural exponential function 自然指数函数natural frequency 固有频率natural geometry 自然几何natural injection 自然单射natural isomorphism 自然等价natural language 自然语言natural logarithm 自然对数natural mapping 自然映射natural number 自然数natural oscillation 固有振荡natural sine 正弦真数natural transformation 自然变换naught 零necessary and sufficient conditions 必要充分的条件necessary and sufficient statistic 必要充分统计量necessary condition 必要条件necessity 必然性negation 否定negation sign 否定符号negation symbol 否定符号negative 负数negative angle 负角negative binomial distribution 负二项分布negative complex 负复形negative correlation 负相关negative definite form 负定型negative definite hermitian form 负定埃尔米特形式negative definite quadratic form 负定二次形式negative function 负函数negative number 负数negative operator 负算子negative parity 负电阻negative part 负部分negative particular proposition 否定特称命题negative proposition 否定命题negative rotation 反时针方向旋转negative semidefinite 半负定的negative semidefinite eigenvalue problem 半负定特盏问题negative semidefinite form 半负定型negative semidefinite quadratic form 半负定二次形式negative sign 负号negative skewness 负偏斜性negative variation 负变差negligible quantity 可除量neighborhood 邻域neighborhood base 邻域基neighborhood basis 邻域基neighborhood filter 邻域滤子neighborhood retract 邻域收缩核neighborhood space 邻域空间neighborhood system 邻域系neighborhood topology 邻域拓扑neighboring vertex 邻近项点nephroid 肾脏线nerve 神经nested intervals 区间套net 网net function 网格函数net of curves 曲线网net of lines 直线网network 网络network analysis 网络分析network flow problem 网络潦题network matrix 网络矩阵neumann boundary condition 诺伊曼边界条件neumann function 诺伊曼函数neumann problem 诺伊曼问题neumann series 诺伊曼级数neutral element 零元素neutral line 中线neutral plane 中性平面neutral point 中性点newton diagram 牛顿多边形newton formula 牛顿公式newton identities 牛顿恒等式newton interpolation polynomial 牛顿插值多项式newton method 牛顿法newton potential 牛顿位势newtonian mechanics 牛顿力学nice function 佳函数nil ideal 零理想nil radical 幂零根基nilalgebra 幂零代数nilpotency 幂零nilpotent 幂零nilpotent algebra 幂零代数nilpotent element 幂零元素nilpotent group 幂零群nilpotent ideal 幂零理想nilpotent matrix 幂零矩阵nilpotent radical 幂零根基nine point circle 九点圆nine point finite difference scheme 九点有限差分格式niveau line 等位线niveau surface 等位面nodal curve 结点曲线nodal line 交点线nodal point 节点node 节点node locus 结点轨迹node of a curve 曲线的结点noetherian category 诺特范畴noetherian object 诺特对象nomogram 算图nomographic 列线图的nomographic chart 算图nomography 图算法non additivity 非加性non archimedean geometry 非阿基米德几何non archimedean valuation 非阿基米德赋值non countable set 不可数集non critical point 非奇点non denumerable 不可数的non denumerable set 不可数集non developable ruled surface 非可展直纹曲面non enumerable set 不可数集non euclidean geometry 非欧几里得几何学non euclidean motion 非欧几里得运动non euclidean space 非欧几里得空间non euclidean translation 非欧几里得平移non euclidean trigonometry 非欧几里得三角学non homogeneity 非齐non homogeneous chain 非齐次马尔可夫链non homogeneous markov chain 非齐次马尔可夫链non isotropic plane 非迷向平面non linear 非线性的non negative semidefinite matrix 非负半正定阵non oriented graph 无向图non parametric test 无分布检验non pascalian geometry 非拍斯卡几何non ramified extension 非分歧扩张non rational function 无理分数non relativistic approximation 非相对性近似non reversibility 不可逆性non singular 非奇的non stationary random process 不平稳随机过程non steady state 不稳定状态non symmetric 非对称的non symmetry 非对称non zero sum game 非零和对策nonabsolutely convergent series 非绝对收敛级数nonagon 九边形nonassociate 非结合的nonassociative ring 非结合环nonbasic variable 非基本变量noncentral chi squre distribution 非中心分布noncentral f distribution 非中心f分布noncentral t distribution 非中心t分布noncentrality parameter 非中心参数nonclosed group 非闭群noncommutative group 非交换群noncommutative ring 非交换环noncommutative valuation 非交换赋值noncommuting operators 非交换算子noncomparable elements 非可比元素nondegeneracy 非退化nondegenerate collineation 非退化直射变换nondegenerate conic 非退化二次曲线nondegenerate critical point 非退化临界点nondegenerate distribution 非退化分布nondegenerate set 非退化集nondense set 疏集nondenumerability 不可数性nondeterministic automaton 不确定性自动机nondiagonal element 非对角元nondiscrete space 非离散空间nonexistence 不存在性nonfinite set 非有限集nonholonomic constraint 不完全约束nonhomogeneity 非齐性nonhomogeneous 非齐次的nonhomogeneous linear boundary value problem 非齐次线性边值问题nonhomogeneous linear differential equation 非齐次线性微分方程nonhomogeneous linear system of differential equations 非齐次线性微分方程组nonisotropic line 非迷向线nonlimiting ordinal 非极限序数nonlinear equation 非线性方程nonlinear functional analysis 非线性泛函分析nonlinear lattice dynamics 非线性点阵力学nonlinear operator 非线性算子nonlinear optimization 非线性最优化nonlinear oscillations 非线性振动nonlinear problem 非线性问题nonlinear programming 非线性最优化nonlinear restriction 非线性限制nonlinear system 非线性系统nonlinear trend 非线性瞧nonlinear vibration 非线性振动nonlinearity 非线性nonlogical axiom 非逻辑公理nonlogical constant 非逻辑常数nonmeager set 非贫集nonmeasurable set 不可测集nonnegative divisor 非负除数nonnegative number 非负数nonnumeric algorithm 非数值的算法nonorientable contour 不可定向周线nonorientable surface 不可定向的曲面nonorthogonal factor 非正交因子nonparametric confidence region 非参数置信区域nonparametric estimation 非参数估计nonparametric method 非参数法nonparametric test 非参数检定nonperfect set 非完备集nonperiodic 非周期的nonperiodical function 非周期函数nonplanar graph 非平面图形nonprincipal character 非重贞nonrandom sample 非随机样本nonrandomized test 非随机化检验nonrational function 非有理函数nonremovable discontinuity 非可去不连续点nonrepresentative sampling 非代表抽样nonresidue 非剩余nonsense correlation 产生错觉相关nonsingular bilinear form 非奇双线性型nonsingular curve 非奇曲线nonsingular linear transformation 非退化线性变换nonsingular matrix 非退化阵nonspecial group 非特殊群nonstable 不稳定的nonstable homotopy group 非稳定的同伦群nonstandard analysis 非标准分析nonstandard model 非标准模型nonstandard numbers 非标准数nonsymmetric relation 非对称关系nonsymmetry 非对称nontangential 不相切的nontrivial element 非平凡元素nontrivial solution 非平凡解nonuniform convergence 非一致收敛nonvoid proper subset 非空真子集nonvoid set 非空集nonzero vector 非零向量norm 范数norm axioms 范数公理norm form 范形式norm of a matrix 阵的范数norm of vector 向量的模norm preserving mapping 保范映射norm residue 范数剩余norm residue symbol 范数剩余符号norm topology 范拓朴normability 可模性normal 法线normal algorithm 正规算法normal basis theorem 正规基定理normal bundle 法丛normal chain 正规链normal cone 法锥面normal congruence 法汇normal coordinates 正规坐标normal correlation 正态相关normal curvature 法曲率normal curvature vector 法曲率向量normal curve 正规曲线normal density 正规密度normal derivative 法向导数normal dispersion 正常色散normal distribution 正态分布normal distribution function 正态分布函数normal equations 正规方程normal error model 正规误差模型normal extension 正规开拓normal family 正规族normal force 法向力normal form 标准型normal form problem 标准形问题normal form theorem 正规形式定理normal function 正规函数normal homomorphism 正规同态normal integral 正规积分normal linear operator 正规线性算子normal mapping 正规映射normal matrix 正规矩阵normal number 正规数normal operator 正规算子normal order 良序normal plane 法面normal polygon 正规多角形normal polynomial 正规多项式normal population 正态总体normal probability paper 正态概率纸normal process 高斯过程normal sequence 正规序列normal series 正规列normal set 良序集normal simplicial mapping 正规单形映射normal solvable operator 正规可解算子normal space 正规空间normal surface 法曲面normal tensor 正规张量normal to the surface 曲面的法线normal valuation 正规赋值normal variate 正常变量normal variety 正规簇normal vector 法向量normality 正规性normalization 标准化normalization theorem 正规化定理normalize 正规化normalized basis 正规化基normalized function 规范化函数normalized variate 正规化变量normalized vector 正规化向量normalizer 正规化子normalizing factor 正则化因数normed algebra 赋范代数normed linear space 赋范线性空间normed space 赋范线性空间northwest corner rule 北午角规则notation 记法notation free from bracket 无括号记号notation of backus 巴科斯记号notion 概念nought 零nowhere convergent sequence 无处收敛序列nowhere convergent series 无处收敛级数nowhere dense 无处稠密的nowhere dense set 无处稠密点集nowhere dense subset 无处稠密子集nuclear operator 核算子nuclear space 核空间nucleus of an integral equation 积分方程的核null 零null class 零类null divisor 零因子null ellipse 零椭圆null function 零函数null hypothesis 虚假设null line 零线null matrix 零矩阵null method 衡消法null plane 零面null point 零点null ray 零射线null relation 零关系null representation 零表示null sequence 零序列null set 空集null solution 零解null system 零系null transformation 零变换null vector 零向量nullity 退化阶数nullring 零环nullspace 零空间number 数number defined by cut 切断数number defined by the dedekind cut 切断数number field 数域number interval 数区间number line 数值轴number notation 数记法number of partitions 划分数number of repetitions 重复数number of replications 重复数number of sheets 叶数number sequence 数列number set 数集number system 数系number theory 数论number variable 数变量numeration 计算numerator 分子numeric representation of information 信息的数值表示numerical 数值的numerical algorithm 数值算法numerical axis 数值轴numerical calculation 数值计算numerical coding 数值编码numerical coefficient 数字系数numerical computation 数值计算numerical constant 数值常数numerical data 数值数据numerical determinant 数字行列式numerical differentiation 数值微分numerical equality 数值等式numerical equation 数字方程numerical error 数值误差numerical example 数值例numerical function 数值函数numerical inequality 数值不等式numerical integration 数值积分法numerical invariant 不变数numerical mathematics 数值数学numerical method 数值法numerical model 数值模型numerical operator 数字算子numerical quadrature 数值积分法numerical series 数值级数numerical solution 数值解numerical solution of linear equations 线性方程组的数值解法numerical stability 数值稳定性numerical table 数表numerical value 数值numerical value equation 数值方程nutation 章动。
2nd International Conference on Computer Engineering, Information Science & Application Technology (ICCIA 2017)The Design of High Speed Data Acquisition System Based on JESD204BYu Wang a, Qingzhan Shi b and Qi FengCollege of Electronic Science and Engineering, National University of Defense Technology,Changsha 410073, Chinaa******************,b********************Keywords: Data acquisition system, JESD204B interface, High-speed ADC.Abstract. Recently, various acquisition systems require data converters to provide higher resolution and sampling rates. The physical layout of parallel interfaces and the bit rate limitations of serial LVDS methods pose technical hurdles for designers. The design is based on the classical architecture of FPGA+DSP+ADC of data acquisition system. The High speed ADC is based on JESD204B interface with four slices and two channels, it can meet the requirements of high-speed acquisition, and high-speed sampling of eight channels. It provides a good method for the design and application of various high-speed acquisition systems, and it effectively solves all kinds of problems in parallel transmission of traditional data acquisition, and brings great engineering application value.1.IntroductionIn our era, the increasing of demand for high data rate application is never stop. This trend leads to the development of high resolution and high sample rate ADC devices. As early as 1991, the United States Navy studied and designed a high-performance programmable signal processor, the architecture of FPGA+DSP had been widely used. Many universities and institutes in China have also developed their own signal processing systems under the FPGA+DSP architecture [1]. Combined with ADC chip, the high-speed acquisition system has also been implemented, but it is difficult for the data transmission to meet the needs of multi-channel, high bandwidth and small size when the traditional data acquisition system adopts parallel transmission mode of multiplex data wires. As a result, the JEDEC international organization has launched a new AD/DA sampling data transmission standard JESD204. So that, the development of the high-speed acquisition system can develop continuously [2].2.The overall hardware designThe design is based on JESD204B interface, designed to achieve high-speed data acquisition system. The design is based on the classical FPGA+DSP+ADC data acquisition system architecture. The FPGA chip uses the XC7VX485T from the Xilinx Virtex-7 series. GTX, its maximum serial speed transceiver, supports the maximum line speed of 12.5Gbps. The DSP chip uses the TMS320C6678 from TI, it integrates 8 arithmetic cores, and the highest processing speed of single core can reach 1.25Gbps. The ADC chip uses the ADC32RF45 from TI, its data is output based on JESD204B interface. As shown in Fig 1, the eight channels sampling signal enters the ADC chip firstly, and then the serial high-speed transceiver GTX is transmitted to the FPGA by the JESD204B interface, then the data is sent to the DSP through SRIO for signal processing operations.FPGA DSPADC x4SRIO PCIEGPIOJESD204B 8Channel FLASH DDR3x4GbpsEthernet FLASH DDR3x2HDMIFig.1 System overall structure diagramIn the design of the data acquisition system, the FPGA’s external interface HDMI, a 19 pin high-speed data interface, is used for data’s communication with external memory. On the board, we connect the four differential signal line of the FPGA’s high speed serial transceiver (GTX) to the HDMI interface. The external high-speed interface of DSP adopts Gigabit Ethernet to realize high-speed data transmission. Both the FPGA and the DSP have an external 256MB Flash memory, In addition, the FPGA has two DDR3 external memory to form the storage space of the 1GB, DSP has four DDR3 memory external to form the storage space of 2GB.3. JESD204B InterfaceIn the field of PC and embedded systems, it has been an empty talk that the method for improving bus bandwidth by raising bus operating frequency under the condition of a parallel bus data width. It cannot be realized at all because of the influence of technology and environment in the actual implementation. Therefore, the communication structure of the serial bus is changed from parallel bus communication. Typically, the ADC is 12~16 bit data lines, and strictly required to be aligned on one edge of the clock. The higher frequency the ADC operating, the greater data offset between the data lines, and then synchronization between data is becoming more difficult. The JEDEC international organizations have fully learned the advantages of PCIE/SRIO and other serial bus communication protocols based on data packet (frame format). The JESD204 protocol was introduced in 2006, it is the a differential pair adopted the CML level, instead of the 12~16 bit parallel data line, realizing serial communication interface and supporting the highest 3.125Gbps data transmission rate of ADC device. In January 2012, the JESD204 bus protocol has been upgraded to the JESD204 B.01 version, the maximum transmission rate of each pair of differential lines is supported by 12.5Gbps [3,4]. Table 1 Comparison of JESD204 with other interfacesNumber of Channels Resolution CMOS Pin Count LVDS Pins Count (DDR) CML Pin Count (JESD204B)1 14 13 14 42 14 26 28 44 14 52 56 68 14 104 112 6Fig.2 CMOS, LVDS, and CML Driver Power ComparisonIn summary, the advantages of JESD204B include the following three points:(1) Decreased in pin number, simplified system design, greatly simplified the wiring between ADC and FPGA(2) Because wiring is simpler and pin number is less, using JESD204B will make the package smaller and simpler.(3) High speed ADC devices consume less power per unit after adopting CML level.At present, the TI, the ADI and other companies have their latest high-speed ADC chip based on the JESD204B interface. ADC32RF45 released by TI, AD9625 released by ADI, and the latest AD9208 released by ADI Company in April 2017, these all belong to the new ADC series adopted with JESD204B interface. In respect of Field Programmable logic device (FPGA), the company, such as Xilinx and Altera, also supports the JESD204B interface. In addition there are JESD204B dedicated clock chip, such as LMK042828, HMC7044 and so on.4.The Key of ADC design interfaceWe can implement the JESD204B protocol by FPGA's GTX interface, to parse the data emitted by ADC correctly. The hardware uses the FPGA’s GTX interface directly, and the GTX is connected with the data-in pin of the ADC. ADC data-out pin as the sending end, FPGA GTX port as the receiving end, to achieve data transmission on the line [5]. The software uses the 8B/10B codec module and the control character detection module which are embedded in the GTX interface.low two bit make up a frame with 16bit data. After framing, the data is encoded by 8B/10B, then it becomes 20 bit. Sending to Serial high-speed transceiver GTX of FPGA, FPGA complete the operation of the 8B/10B decoding and the analysis of JESD204B protocol. Setting the ADC32RF45 sample clock to 2.5GHz, the rate corresponding to the encoding at all levels is shown below.Table 2 Comparison of JESD204BClock/GH z Data-width/bit Rate/Gbp sRemark Original data 2.5 14 8.4 ADC Sampled DataFraming 2.5 16 10 Zero-paddingCoding 2.5 20 12.5 8B/10BThe ADC is dual channel, each channels has 4 lanes, that is, 4 pairs of CML data lines. As can be seen from the chart above, ADC eventually sends the sampled data at a rate of 12.5Gbps, GTX, the receiving rate of the FPGA side should also be set to 12.5Gbps.5. Clock designJESD204B begins with the edge of the clock signal to identify synchronization. And through a certain handshake signal, the sender and receiver can correctly recognize the frame length and boundaries. Therefore, the clock signal and its timing relation are extremely important to JESD204B. The following is a multi-device synchronization solution for the JESD204B system, the Device Clock is the main clock for the device operation. A clock that is usually sampled in a digital to analog converter or a clock with integer multiples. The frame and multi frame clock of the protocol itself are also based on Device Clock. SYSREF is the edge of the Device Clock used to indicate different converters or logic, or the reference delay between different devices.In the JESD204B system, the synchronization of data converters can be broken down into four basic requirements. These requirements are vividly depicted in Fig.4.(1) The phase alignment of the device clock is implemented on each data converter;(2) The setting and holding time of the SYSREF (relative to the device clock) are met on each data converter and logic element;(3) An appropriate resilient buffer release point is selected in the JESD204B receiver to ensure deterministic delay; (4) Need to meet the SYNC signal timing requirements when necessary. A D CA D CA D CA D C Data SYNC DataSYNC Data SYNCDevice Clock SYSREF Device ClockSYSREF Device Clock SYSREFDevice ClockSYSREFLogic DeviceClock Distirbution DataSYNCFig.4 Multi device synchronization solution for JESD204B systemADI and TI have high performance clock jitter attenuator with JESD204B, such as HMC7044, LMK04828 and so on. Their Device Clock, and SYSREF are paired output, its output timing meets its timing requirements, and its application is relatively simple.6.ConclusionThis paper utilizes the advanced high-speed ADC with JESD204B interface, combine the latest ADC chip and Xilinx 7 Series resources, and proposes the design of high-speed data acquisition system based on JESD204B. This paper first describes the overall design of the system, and then we detailed for each module design. We first solve the core processing module of FPGA+DSP. Both of FPGA and DSP communicate with each other through SRIO, FPGA pretreatment data is sent to the DSP for signal processing. Utilizing existing technology and hardware, a high-speed data acquisition system is designed with the JESD204B interface ADC which has higher resolution and higher sampling rate (3Gbps or so). It can be well suited to eight channel high-speed sampling, the design is miniaturized and the wiring is simpler. FPGA resource consumption is reduced by about half of resources compared to traditional parallel data lines, it has great prospect of engineering application. References[1] Ran Yan, XI Pengfei. High Speed Serial Data Acquisition System Based on JESD204 Protocol [J].Electronic Sci. & Tech. 2015, 28(5):17-19[2] Zhou Yuxuan, Clock Circuit Design of 2.5 GSPS High Resolution Data Acquisition System [D].UESTC, 2016[3] ADI. JESD204B Survival Guide [M]. [USA]: ADI, 2013[4] ADI. JESD204B serial interface clock requirements and their implementation [M]. [USA]: ADI,2013[5] Xilinx. 7 Series FPGAs GTX/GTH Transceivers [M]. USA: Xilinx, 2016.。
工业工程专业英语--翻译工业工程的真正价值 Real IE ValueIn addition, the IE now has a greater opportunity to concentrate on any one of a broad variety of areas that many companies now recognize as individual departments-including simulation, operations research, ergonomics, material handling and logistics.值得一提的是，工业工程现在有更多的机会去集中于现在许多企业已经视为独立的学科的众多领域中的一个-----包括防真学、运筹学、人因学、物料搬运和物流学。
Work-measured Labor Standards 基于作业测量的劳动标准If you are a manufacturer, chances are you have a bill-of-materials (BOM) system to determine standard parts cost. Do you also have an equivalent bill-of-labor system to determine standard labor cost?如果你是一个制造商，你有可能会有一个物料清单系统来确定标准件的成本。
你是否也能得到类似的劳动力清单系统来确定标准的劳动成本,Time study——The most widely used tool to develop standard times is still time study. Time study reflects what is happening in your job or project. It is also easy to learn and use. Now, the PC has made summarization of time study data a matter of seconds instead of hours.时间研究----用来开发标准时间使用最广泛的工具依然是时间研究。
本文网址：/cn/article/doi/10.19693/j.issn.1673-3185.03122期刊网址：引用格式：宋利飞, 许传毅, 郝乐, 等. 基于改进DDPG 算法的无人艇自适应控制[J]. 中国舰船研究, 2024, 19(1): 137–144.SONG L F, XU C Y, HAO L, et al. Adaptive control of unmanned surface vehicle based on improved DDPG algorithm[J].Chinese Journal of Ship Research, 2024, 19(1): 137–144 (in Chinese).基于改进DDPG 算法的无人艇自适应控制扫码阅读全文宋利飞1,2，许传毅1,2，郝乐1,2，郭荣1,2，柴威*1,21 武汉理工大学 高性能船舶技术教育部重点实验室，湖北 武汉 4300632 武汉理工大学 船海与能源动力工程学院，湖北 武汉 430063摘 要:［目的］针对水面无人艇（USV ）在干扰条件下航行稳定性差的问题，提出一种基于深度强化学习（DRL ）算法的智能参数整定方法，以实现对USV 在干扰情况下的有效控制。
［方法］首先，建立USV 动力学模型，结合视线（LOS ）法和PID 控制器对USV 进行航向控制；其次，引入DRL 理论，设计智能体环境状态、动作和奖励函数在线调整PID 参数；然后，针对深度确定性策略梯度 （DDPG ）算法收敛速度慢和训练时容易出现局部最优的情况，提出改进DDPG 算法，将原经验池分离为成功经验池和失败经验池；最后，设计自适应批次采样函数，优化经验池回放结构。
［结果］仿真实验表明，所改进的算法迅速收敛。
同时，在训练后期条件下，基于改进DDPG 算法控制器的横向误差和航向角偏差均显著减小，可更快地贴合期望路径后保持更稳定的路径跟踪。
［结论］改进后的DDPG 算法显著降低了训练时间成本，不仅增强了智能体训练后期的稳态性能，还提高了路径跟踪精度。
第 21 卷 第 8 期2023 年 8 月太赫兹科学与电子信息学报Journal of Terahertz Science and Electronic Information TechnologyVol.21，No.8Aug.，2023基于非均匀采样的DTMB-A信号模糊函数抑制方法宋佳乐，万显荣*，张勋，易建新，占伟杰(武汉大学电子信息学院，湖北武汉430072)摘要：新一代数字电视地面广播传输演进标准(DTMB-A)是国标数字电视地面广播信号(DTMB)演进的新一代标准，具有带宽大、抗多径能力强等优点，可作为一种新型的外辐射源雷达机会照射源。
本文阐述了DTMB-A信号模糊函数特性，详细分析了其帧内及帧间模糊副峰的形成机理，分析结果表明DTMB-A信号中确定性重复结构(同步信道、保护间隔等)是造成模糊副峰的主要因素。
对此，提出一种基于非均匀采样的模糊副峰抑制方法。
该方法具有计算复杂度低、易于并行实现等优点。
仿真结果证明所提方法能够将DTMB-A模糊函数修正为理想的图钉型，验证了该方法的有效性，为基于DTMB-A信号的外辐射源雷达目标探测研究提供了方法。
关键词：外辐射源雷达；模糊函数；中国地面数字电视传输标准的演进版本；非均匀采样中图分类号：TN958.97 文献标志码：A doi：10.11805/TKYDA2021102DTMB-A Signal Ambiguity Functions suppression method based onnon-uniform samplingSONG Jiale，WAN Xianrong*，ZHANG Xun，YI Jianxin，ZHAN Weijie(School of Electronic Information，Wuhan University，Wuhan Hubei 430072，China)AbstractAbstract：：Digital terrestrial Television Multimedia Broadcasting-Advanced(DTMB-A), is a new type of illuminator of opportunity for passive radars, which has broad bandwidth and excellentadaptability against multipath effect. In this paper, DTMB-A signal Ambiguity Function(AF) isconcluded and the mechanism of intra-frame and inter-frame ambiguity peaks is researched bytheoretical derivation and simulation verification. The analysis shows that the period deterministic framestructure(the synchronization channel and guard interval) is the main factor that causes the ambiguitysub-peaks. Therefore, a DTMB-A signal ambiguity functions suppression method is proposed by usingnon-uniform sampling, which has low computational complexity and is convenient for parallelcomputing. Simulation results show that this method can suppress DTMB-A signal Ambiguity Functionsinto almost ideal thumbtack shape effectively, which is the foundation of detecting target on DTMB-Apassive radar.KeywordsKeywords：：passive radar；Ambiguity Function；Digital terrestrial Television Multimedia Broadcasting-Advanced(DTMB-A)；non-uniform sampling外辐射源雷达是一种自身不发射电磁信号，利用第三方辐射的机会信号实现目标探测的双/多基地雷达，它具有节约频谱、静默探测、军民两用等诸多优势，备受国内外研究学者关注[1-2]，在传统雷达的研究基础上[3-4]一系列技术均得到了长足发展。
重要性采样算法的有效性和可靠性分析重要性采样（Importance Sampling）算法是一种常见的概率推断方法，用于估计目标分布的期望值或者计算归一化常数。
在许多概率推断问题中，我们常常希望对一个分布的性质进行评估，但是由于难以直接对目标分布进行采样，重要性采样算法便应运而生。
重要性采样的核心思想是通过从一个简单且容易采样的分布中生成样本，对目标分布进行近似估计。
这种方法广泛应用于统计学、机器学习和自然语言处理等领域中。
该算法的有效性主要体现在两个方面：采样效率和估计准确性。
首先，重要性采样在采样效率方面具有显著优势。
通过从一个已知分布中采样，我们可以得到更多样本，并且样本的生成可以通过一些简单而高效的算法实现。
相对于其他推断方法（如马尔科夫链蒙特卡洛方法和变分推断方法），采样效率更高，可以更快地获得足够数量的样本用于估计。
其次，在估计准确性方面，重要性采样算法在一些情况下可能存在一些问题。
重要性采样的核心是通过对生成的样本进行加权估计来近似目标分布的期望值。
然而，当生成的样本与目标分布相差较大时，估计的方差可能会较大。
特别是当生成的样本位于目标分布的支撑集外部时，重要性采样的估计可能会发散甚至无法收敛。
为了提高重要性采样的可靠性，研究者们提出了一系列改进算法。
其中一种常用的方法是调整权重。
通过对样本的加权，可以减小估计的方差。
例如，通过重采样（resampling）方法，从生成的样本中重新采样，使得“重要”的样本具有更高的权重，从而提高估计的准确性。
另一个方法是使用改进的采样策略，如Metropolis-Hastings算法或Gibbs采样算法，以更好地逼近目标分布。
此外，对于复杂的概率模型，研究者们还提出了一些近似重要性采样算法，如变分重要性采样（Variational Importance Sampling）和确定性重要性采样（Deterministic Importance Sampling）。
The Application for Harmonic Superposition in Wind Farm Using the Methodology of Monte-Carlo Jiayi Wang1, Yanchi Zhang1,*, Hongkun Yang2, Xiangping Xu1 and Yi Zha11School of Electrical Engineering, Shanghai Dianji University, Shanghai 201306, China2Shanghai Electric Wind Power Equipment Co., Ltd, Shanghai 200241, China*Corresponding authorAbstract—The harmonic aggregation in wind power generation is widely concerned in engineering practice. In this paper, large volumes of voltage and current data in wind farm was measured and analyzed for exploring the distribution rules of harmonic current amplitude and phase, based on which, the probabilistic statistical model of harmonic current in wind farm was set up. And the superposition of harmonic in wind farm was predicted and evaluated with Monte-Carlo method. Simulation shows that the calculation of harmonic superposition with Monte-Carlo method has strong reliability and maneuverability. This method can be used to calculate the mean value of the superposition of harmonic and predict the harmonic aggregation at extreme situations.Keywords-wind farm; harmonic superposition; harmonic current phase; probability distribution; monte-carlo methodI.I NTRODUCTIONThe renewable energy industries have been greatly developed in recent years due to the global energy crisis. Among them, wind power has become one of the dominate renewable energy resources because of its low cost and high capacity. According to the latest report of world wind energy (WWEA)[1], the global installed capacity has reached 370GW since the end of 2014. Meanwhile, the installed scale of wind farms is gradually increasing and the rapid expansion of the nonlinear load, causing the world’s attention on power quality issues.Increasing installed capacity of wind power plant has contributed to the variation of harmonic current distortion rate at the side of main transformer of wind farm. According to the testing reports which manufacturer released, in ideal working condition of balance grid voltage, total current distortion rate will reach 3% with rated power of wind turbines, but reach more than 10% during actual operation. Otherwise , it is hard to meet the relevant standard of grid integration[2-4].The main reasons of this phenomenon are aroused from the discreteness of harmonic current phase angles produced by each unit in power plant, which makes the situation of same phase angle happened and leads to increasing current distortion rate, poor power quality, incidental resonance with grid, overcurrent and overvoltage. At the same time, further harmonic response will happened in resonance and it might damage the electrical equipment more seriously. Under these situations, the improvement of power quality has become the key point in wind power research.Previous research work on wind power harmonic current problem mainly concentrated on converter control strategies in the single-unit system[5-6]. But in wind farm, harmonic current has recently made impact on power grid. So problems related to harmonic resonance have been analyzed through different analysis methods[7].Nowadays, the growing use of power electronics systems in the grid verifies the importance of the research of harmonic problems[8].The deterministic and stochastic characterization of harmonic currents amplitude and phase angle is analyzed through an 18MW wind farm[9].As we all know, few research on the harmonic model of wind farm and the analysis of harmonic current have been performed, whereas, the research on harmonic current and traction load system has developed a lot [10-13].In order to understand the harmonic distribution of wind farms and establish wind farms harmonic probability model precisely, this paper develops the study of harmonic model on the basis of the large volumes of measured data in wind farms, using the stochastic process theory and numerical analysis theory. This paper will simulate the wind farm harmonic phase superposition situation with Monte-Carlo method, and analyze the factors affecting the grid at the point of common coupling (PCC). To suppress the harmonic current of wind farm connected to power grid, providing a reliable assessment can reduce the loss of human and financial resources in the post-equipment renovation project.II.G ENERATING P RINCIPLES O F T HE D OMINIANTH ARMONIC C OMPONENTThe main harmonic source of doubly-fed Induction Generator (DFIG) is the converter, the control strategies through the closed loop makes the output waveform and the target positive sequence identical, there are mainly three types of closed-loop control, hysteresis control, sinusoidal pulse width modulation (SPWM) and space voltage vector pulse width modulation (SVPWM).In the three ways of closed-loop control, the 6N+1 harmonic generation is inevitable due to the influence of the dead time of the IGBT switch. Considering the situation of stator and rotor working together at the same time in DFIG, the three-phase AC voltage is set up as follows:International Conference on Test, Measurement and Computational Method (TMCM 2015)()1cos i ms m i m se E t ωθ∞==+∑∑ (1)where i is a , b , c , three phase and s is p ,n ,0 which represent positive sequence; negative sequence and zero sequence respectively.During rectification and DC voltage represented as follows:()()11110.5((12cos(2/3)sin(())(12cos(2/3)sin(()))dc ms nu m n sm a m a u E A n s n t n s n t πωωθπωωθ∞∞===++×++++−×−+∑∑∑ (2) where nu A is the corresponding coefficient of voltage switching function for converter control and 1ω is the modulation wave frequency.At present, space vector control as the most common method is used in convertor control. It has higher utilization ratio for DC voltage, easier performance in digitization and the relative lower harmonic than other methods. At the same time, considering the process of grid integration which power transits from DC side to grid-side convertor, the space vector control is used by similar control method of phase control by six IGBTs of three phase inverter bridge. The analysis method of phase controlled inverter keeps on being used to express. The switching function of three-phase 6 pulse converter is represented as follows:126126121cos()cos((61))cos((61))ia j j j s k t k j t k j t ωωω∞−+==−−−+∑ (3)wherei k Indicates the coefficient of each component and2ωrepresents modulation frequency of the grid-side converter.DC current corresponding to (3) is expressed as:(6)1(61)1(61)1(61)1(61)111sin(6)(sin((62))sin((62)))(sin((61))sin((61)))dc dc k kp k k k kn k kn k mm km k mm k m km i I I k t I k t I k t Ik t t I k t t ωθωθωθωωθωωθ∞∞+==−∞∞+−===++++++−+++−++++−++∑∑∑∑ (4)In (4), the results is divided into four parts which are separately the corresponding effect of DC component, the influence of fundamental voltage positive sequence, negative sequence and each harmonic component in AC side of rectifier on the current of DC side.The output voltage of the grid-side converter is (B, C are similar):a dc ia i i s = (5)Put(3),(4)into(5),we can get dominant harmonic components.III. M EASUREMENT A ND A NALYSIS O F H ARMONIC D ATAA. Method of MeasurementThe measurement method on power quality of wind power mentioned in the designing fourth version of IEC61400-21 will be used in this paper. Its basic calculation method is to analyze the 200ms data within the 10 cycles by FFT when the sampling frequency ranging from 10 kHz to 20 kHz. And then the amplitude and phase of the harmonics are obtained. FFT as a mature algorithm, the basic principle is not introduced in detail.In this paper, the basic calculation process of the collected 2048 data points in each section was analyzed by FFT.(k)FFT[x(n)]n 0,1,2,2047X ==L (6)where x(n)is one of the sampling values of the three phase voltage and current A B C.The plural result (k)X by FFT is acquired. Through the results, we can calculate the amplitude and phase angle values of harmonic voltage and current. During MATLAB programming, the resolution frequency of 5Hz is chosen. ABS is calculation of amplitude and Angle is function of phase angle. The process of calculation is as follows: Voltage DC component:dc U =(0)/2048X (7)Fundamental voltage amplitude:1U =ABS[(10)]/1024/1024X (8)Fundamental voltage phase:1Im[X(10)]U =Angle[(10)]Re[X(10)]X arctgα∠== (9)N th harmonic voltage amplitude:U =ABS[(10)]/1024n X n (10)N th voltage harmonic phase:U =Angle[(10)]n n X n α∠− (11)N th harmonic current phase:=Angle[(10)]n n i I X n α∠− (12)In the actual data analysis, the accuracy of the phase value of the fundamental voltage should be in a high standard because there is no uniform time standard based actual sampling data of each wind turbine units when the sampling work happened. For acquiring the phase relationship of different frequency harmonics of output current in wind turbine, calculation must be based on a common time starting point. At this time, harmonic currents of each units in wind farm gather at the point of common coupling (PCC)-the main transfers side. During the progress of calculation, each wind turbine should be the same type, the transformer connected should be same as well. Transmission distance of each unit in the wind farm is slightly different, so the total impedance has little difference. Then the fundamental phase is the reference value when calculating the phase value of each harmonic. Besides, the accuracy of calculation for each harmonic would be highly influenced by very small deviation of fundamental phase.B. Analysis of Harmonic Based on One Wind TurbineThe gathered data in this paper is from wind farm including 50 sets of Doubled-Fed wind power generator. The framework of a DFIG is shown in FIGURE I. Cable lines carry the output current of each wind turbines to the mediumvoltage collector with 35/0.69kV transformers. Throughtransmission line and 110/35kV transformer, currents are fed into the grid. IhPCC Iwt-hWT DFIG...N=50WTs...0.69/35kV 0.69/35kV35/110kV Iwt-hThe grid50Hz System Iwt-hPower analyzermeasurementmain transformerFIGURE I. WIND FARM TOPOLOGY.One 2MW Doubled-Fed wind power generator is randomly selected for real-time data acquisition. 103 groups of data during 14 days , which is three phase voltage and current output waveform of the wind turbine in wind speed between 3m/s to 10m/s ,are obtained. The time span of each group is 10s and the probability density functions of wind speed andpower are separately shown in FIGURE II.FIGURE II.PROBABILITY DENSITY FUNCTION OF WIND SPEEDAND POWER OUTPUT DATA.The data segment of 200ms intercepted from collected data by DEWE soft is analyzed and calculated. Its sampling frequency is 4kHz and the frequency resolution is 5Hz. Through statistical calculation, the probability density function (PDF) of 6n ±1th harmonics are shown in FIGURE III, which distribution characteristics is approximately considered as the normal distribution. As sample size increasing, the statistics are closer to the normal distribution. So probabilistic models of harmonic amplitude in wind farm have been effectively built.FIGURE III. STATISTICAL ANALYSIS OF HARMONIC CURRENTDURING THE WIND SPEED RANGED FROM 2.8M/S TO 9.2M/S IN 2MW DFIG. C. Harmonic Distribution Characteristic of Wind FarmThe relations between 6n ±1th harmonic current amplitudeand phase produced by wind turbines in wind farm are shown in FIGURE.IV. Obviously, the phases of the fifth and seventhharmonic current are relatively stable and have less fluctuation.And yet, 11th ,13th 17th and 19th harmonic current amplitudes change little, but the phase have large fluctuations. It resultsfrom the features of more than 11th harmonic which are high frequency and short period. A slight error caused by the measurement of the fundamental phase angle can make phase angle generate a lot of volatility.FIGURE IV. DISTRIBUTION OF HARMONIC CURRENT IN WINDFARM.IV. S TATISTICAL M ODEL OF H ARMONIC I N W IND F ARMConsidering situation of the output current in box transformer substation during operation of wind turbine, when harmonic currents from different wind turbines go through transmission lines and gather together, the output harmoniccurrent of main transformer will be thought to be approximately the summation of them. N thharmonic currentcan be expressed as:11NNn jn jn t t j j I X j Y X jY ===+=+∑∑ (13)The distribution of the harmonic current in the wind farm is mainly dependent on the statistical characteristics of the harmonic current of the single WT (PDF of amplitude and phase). For 50*2MW DFIGs in wind farm, their dominant harmonic components (such as 5th , 7th , 11th ,13th , 17th and 19th harmonics) are independent respectively. According to the central limit theorem, j X and j Y can be obtained and approximately obey the normal distribution. jn X andjn Yhave own physical characteristics, so their expectation and variance can be almost a certainty. As long as value of N is large enough, we can deduce and attain that j X and j Y can obey normal distribution based on law of large numbers and central limit theorem. Through statistics, the dominantharmonic component in wind farm are shown in FIGURE V.FIGURE V. STATISTICAL ANALYSIS OF THE HARMONIC CURRENTX –Y PROJECTION.The joint distribution of i X and j Y is determined by the following 5 parameters: t X μ,t Y μt X σ,t Y σ,t ρ. Amongthem, t X μand t Y μ are the mathematical expectation of t X and t Y ;t X σand t Y σare the standard variance of t X and t Y ;t ρisthe correlation coefficient of t X and t Y [9,14]. Joint density function is expressed as:22222()11(,)exp{[22(1)2()()()]}t t t tt t t tttt X xy t t X Y t Xt t X t Y t Y X YY X f X Y X Y Y μπσσρσρμμμσσσ−−=−−−−−+(14) The expectation and variance of the algorithm are no longer duplicated, and the joint distribution of the 5 parameters can be obtained by the following:1tj N X X j μμ==∑;1tj N Y Y j μμ==∑;21/21()tjNX Xj σσ==∑; 21/21()t j NY Y j σσ==∑; 1cov(,)/(,)()/()ttj j t tNt t t X Y tj X Y X Y j X Y ρσσρσσσσ===∑ (15)Thus, the probability density function of the vector h I will be acquired. cos t X r θ=and sin t Y r θ=will be pluggedinto (14) and get the joint density function: 20()(cos ,sin )r f r f r r rd πθθθ=∫(16)By calculation, when the harmonic current amplitude and phase value produced by the power generating units are satisfied with the assumption, that is the real and imaginary parts of the harmonic currents can satisfy the condition of theindependence for each other and the same distribution, the distribution function of harmonic current and the statistical characteristics of the harmonic current amplitude can be obtained.V.S IMULATING B ASED O N M ONTE -C ARLO M ETHODThe basic principle of Monte Carlo method is based on Bernoulli's law of large numbers. If the probability {}i P X of random events i X , in the independent sampling N, the frequency of the incident is followed as m/N(m is the number of events i X in n trials)[15,16]. For any small positive 0ε> given, we get:{{X }}1lim iN mP P N ε→∞−<= (17)That is to say, when the number N of independent experiments is large enough, the frequency of the m/N is convergent to {}i P X . This ensures the probabilistic convergence of the simulation method.For the phase distribution of the wind farm and the harmonic data of the single unit under different wind speeds acquired, the model of the dominant harmonic component in the wind farm is established. The process diagram of simulating specifically with Monte-Carlo method is shown in FIGURE VI. by this method, the harmonic current summation at the point of common coupling can be obtained, and the power quality can be effectively evaluated. The extreme situation of the harmonic current in the wind farm can be analyzed and judged, meanwhile the mean values are acquired.FIGURE VI. THE PROCESS DIAGRAM OF SIMULATION WITHMONTE-CARLO METHOD.Utilizing Monte-Carlo method can obtain the evaluationvalues of the harmonic current at the point of common coupling. Results of simulation are shown as FIGURE VIIAfter the harmonic currents go through the 0.69/35kV box transformer substations, the mean value of the 5thand 7thharmonic currents at the low-voltage side of the main transformer is 8 to 9 A, while 11th , 13th ,17th and 19th harmonic currents are superimposed around the average value of 2A. It is not hard to see that the dominant harmonic source of the wind power system is 6n ±1harmonics caused by the dead time in the converter control. In addition, we have evaluated the worst condition of the harmonic current in power grid, that amplitude peaks of 5th and 7th harmonics is over 16A and 11th , 13th , 17th and 19th harmonic current peaks reach 5A. It fully shows the importance of study on the phase of the network harmonic current. In order to evaluate the variation of the harmonic current in wind farm, it’s important to establish the statistical model by actual measurement data. Meanwhile, according to P =n/N , combined with the actual requirements of the harmonic current, its probability exceeding the limit value will be acquired, and it’s convenient to assess and predict power quality problems in the wind farm. The superposition result of the harmonics is also similar to the normal distribution, which provides a strong basis for establishing harmonic model of the wind farm.FIGURE VII. PROBABILITY DENSITY PLOT OF SIMULATION WITHMONTE-CARLO METHOD.VI. C ONCLUSIONA systematic method has presented in this paper for analyzing and evaluating the harmonic current in wind farm. The key contributions of the paper are:(1) utilize measured data to analyze the amplitude and phase angle of the dominant harmonic current components and acquiring its PDF, (2)set uo the statistic model of harmonic current of wind farm suitable for calculation of harmonic current (3) predict and evaluat the harmonic current values at the point of common coupling based on the Monte-Carlo method.This comprehensive method shown in this paper is benefit to forecast and evaluate power quality at PCC, which can be used to avoid the impact of harmonic and reduce the investment of regular maintenance for the company. The evaluation method not only creates a strong foundation to reduce harmonic superposition by phase interleaving, but also provides a practical reference for adjusting the wind power equipment and the optimization of control strategy.A CKNOWLEDGMENTThis work has been funded by the National Natural Science Foundation of China (51277119).This work is supported by Shanghai education commission, science and technology innovation fund project(10Y217).R EFERENCES[1]WWE Association, "WWEA half year report 2014," (2014)[2]IEC 61400-21 Wind turbine generator systems, Part 21: Measurementand assessment of power quality characteristics of grid connected windturbines.[3]IEC 61000-3-6 Electromagnetic Compatibility (EMC) Part 3: Limits-Section 6: Assessment of emission limits for distorting loads inMW andHV power systems-Basic EMC Publication[4]IEC 61000-4-7 Electromagnetic compatibility (EMC) Part 4-7: Testingand measurement techniques-General guide on harmonic and inter-harmonic measurements and instrumentation, for power supply systemsand equipment connected thereto.[5]Chen Y, Tong Y, Jin X. A novel algorithm of SVPWM harmonicanalysis[C]//Industrial Electronics and Applications, 2007. ICIEA 2007.2nd IEEE Conference on. IEEE, 2007: 1752-1755.[6]Hughes F M, Anaya-Lara O, Jenkins N, et al. Control of DFIG-basedwind generation for power network support[J]. Power Systems, IEEETransactions on, 2005, 20(4): 1958-1966.[7]Hasan K N M, Rauma K, Rodriguez P, et al. An overview of harmonicanalysis and resonances of large wind power plant[C]//IECON 2011-37th Annual Conference on IEEE Industrial Electronics Society. IEEE,2011: 2467-2474.[8]Yu N, Nian H, Quan Y. A novel DC grid connected DFIG system withactive power filter based on predictive current control[C]//ElectricalMachines and Systems (ICEMS), 2011 International Conference on.IEEE, 2011: 1-5.[9]Sainz L, Mesas J J, Teodorescu R, et al. Deterministic and stochasticstudy of wind farm harmonic currents[J]. Energy Conversion, IEEETransactions on, 2010, 25(4): 1071-1080.[10]Papathanassiou S, Papadopoulos M P. Harmonic analysis in a powersystem with wind generation[J]. Power Delivery, IEEE Transactions on,2006, 21(4).[11]Vasile R, Galve F, Zambrini R. Spectral origin of non-Markovian open-system dynamics: A finite harmonic model without approximations[J].Physical Review A, 2014, 89(2): 022109.[12]Xie S, Li Q, Zhao L. Study on harmonic distribution characteristic andprobability model of the traction load of electrified railway[J].PROCEEDINGS-CHINESE SOCIETY OF ELECTRICAL ENGINEERING, 2005, 25(16): 79.[13]Cella U, Tran T, Nussey P, et al. Modelling of traction power system forevaluation of harmonic distortion in relation to route capacity[C]//CORE2014, Rail transport for a vital economy, conference on railwayengineering, Adelaide, South Australia, 5-7 May 2014. 2014.[14]Baghzouz Y, Tan O T. Probabilistic modeling of power systemharmonics[J]. Industry Applications, IEEE Transactions on, 1987 (1):173-180.[15]Kazibwe W E, Ortmeyer T H, Hammam M. Summation of probabilisticharmonic vectors [power systems][J]. Power Delivery, IEEE Transactions on, 1989, 4(1): 621-628.[16]El-Khattam W, Hegazy Y G, Salama M M A. Investigating distributedgeneration systems performance using Monte Carlo simulation[J]. Powersystems, IEEE transactions on, 2006, 21(2): 524-532.。
Deterministic Sampling Methods for Spheres and SO(3) Anna Yershova Steven ValleDept.of Computer ScienceUniversity of IllinoisUrbana,IL61801USA{yershova,lavalle}@AbstractThis paper addresses the problem of generating uni-form deterministic samples over the spheres and the three-dimensional rotation group,SO(3).The target applications include motion planning,optimization, and verification problems in robotics and in related areas,such as graphics,control theory and computa-tional biology.We introduce an infinite sequence of samples that is shown to achieve:1)low-dispersion, which aids in the development of resolution complete algorithms,2)lattice structure,which allows easy neighbor identification that is comparable to what is obtained for a grid in R d,and3)incremental qual-ity,which is similar to that obtained by random sam-pling.The sequence is demonstrated in a sampling-based motion planning algorithm.1IntroductionMany important algorithms developed in robotics and related areas require careful sampling over spheres.In recent years,the paradigm of sampling-based motion planning has led to algorithms that can solve many challenging problems by combining colli-sion detection,search algorithms,and sampling strate-gies over the configuration space.General sampling over spheres arises in many forms of planning and op-timization in which some number of directions are lo-cally explored.For example,some potentialfield ap-proaches[3,10]involve sampling local directions to obtain an approximate gradient descent.The exact expression of the gradient may be too costly or even unavailable.One important special case of sampling over spheres is sampling over the3D rotation group, SO(3),which involves sampling over half of the three-sphere,S3.One of the main motivations for thispaperFigure1:Distribution of points on the sphere S2gen-erated by a grid(Sukharev[20])on each spherical face.is the problem of motion planning for a rigid body in R3.We are particularly interested in the development of deterministic sampling methods.Although most existing motion planning methods currently use ran-dom sampling,they are limited to probabilistic forms of completeness.With deterministic sampling,reso-lution completeness guarantees are possible.This is particularly valuable in the area of system verifica-tion,in which one must guarantee that a system be-haves correctly under all possible trajectories.The intractability of most of these problems leads natu-rally to sampling based approaches.While it may be valuable to verify a system down to some level of res-olution,random sampling might leave doubts about whether the space was adequately covered.In some cases,deterministic sampling has even led to practical performance improvements in comparison to random sampling[13,14,15].The techniques presented in the present paper build on recent work to develop uniform, deterministic sampling techniques for motion planning [6,12,13].1The particular problem of sampling over spheres presents many unique challenges.The vast majority of sampling literature considers placing points in a unit d-dimensional cube,[0,1]d⊂R d(see[12,15]).This might correctly capture some configuration spaces that arise in robotics;however,the majority of appli-cations involve other topological spaces,such as R P3, which arises from rigid body rotations,or toroidal manifolds,which arise from a series of revolute joints of a manipulator.In these cases,special sampling techniques should be developed because quality mea-sures for sets of samples depend on the topology.For example,the maximum distance that a configuration could be from its nearest sample depends on the met-ric,which is induced partly by the topology.In addition to topological issues,the way that a configuration space is parameterized is of critical im-portance to defining notions of uniformity.A col-lection of samples that are uniform with respect to one parameterization of the configuration space might seem extremely biased using another parameteriza-tion.It might seem that there is no way to avoid this frustrating issue,but fortunately for the case of SO(3),there is an intrinsic notion of uniformity that is given by the Haar measure[7](this will be defined in Section2).Using this notion,the natural parameter-ization of SO(3)is the set of unit quaternions(with antipodal identification),and our sampling methods will be developed to achieve rigorous notions of uni-formity in this case.To maximize the potential for impact on motion planning and related areas,our goal has been to de-velop a sampling method that achieves1)uniformity, 2)lattice structure,and3)incremental quality.Uni-formity means good covering of the space is obtained without unwanted bias,clumping or gaps.This can be formulated in terms of optimizing discrepancy or dis-persion[14,15,4].The uniformity notion considered here is actually more“uniform”than what is obtained by random ttice structure means that for every sample,the location of nearby samples can eas-ily be determined as part of a regular pattern(as in neighbors on a grid,for example).Incremental quality means that if the sampling method is considered as an infinite sequence,then the sequence may be truncated after anyfinite number of samples and good coverage will be obtained.This is an important characteris-tic of pseudo-random number sequences,making them desirable for many past motion planning algorithms [1,5,9,19,22].We would like to obtain the same behavior,even though the sequence is deterministic, uniform,and has lattice structure.2Quality Measures for the Distribu-tions of Points on SpheresWe consider generating samples over spheres and SO(3).Let S d represent a d-dimensional sphere,em-bedded in R d+1asS d={x∈R d+1| x =1}.The set of all rotations in R3is denoted as SO(3), which is defined as the set of all3×3orthonormal ma-trices.It will be helpful to sometimes represent SO(3) as the set,H,of unit quaternions,each of which is ex-pressed as h=a+bi+cj+dk,with the identification h∼−h[11].Note that it appears that H=S3, except that antipodal points on S3are identified in the definition of H.This leads to a close relationship between sampling on sphere and sampling on SO(3).Now that the spaces have been defined,the next task is to define the quality of samples.Consider sphere S d over which thefinite set of points A is gen-erated.Definition2.1For afinite point set A generated over the sphere S d the discrepancy of A with respect to a given family R of subsets of S d,called ranges,is defined byD R(A)=supR∈R|A∩R||A|−µ(R),whereµdenotes the rotation invariant measure of the sphere S d in Euclidean space R d+1,and|·|applied to afinite set denotes its cardinality.In the case of SO(3)the measure defined on S3as above corresponds to the Haar measure defined over the set of all rotation matrices.The range spaces that are usually considered on the sphere are the set of spherical caps,i.e.,intersections of the sphere with half spaces;or the set of spherical slices,i.e.,intersections of two half-spheres[4,16].Definition2.2The dispersion of afinite set A is de-fined byd R(A)=supq∈S dminp∈Aρ(q,p),in whichρis a rotation invariant metric over S d.Having these definitions of uniformity in mind,in what follows we propose a general approach to sam-pling on spheres and SO(3).As a particular example we show how to generate a low-dispersion and low-discrepancy sample set which has additional useful2properties:it is incremental,has lattice structure,and it can be efficiently generated.We show how these samples can be applied to the problems of motion planning.3Exploiting the Regularity of Pla-tonic SolidsOur general approach to sampling is based on Pla-tonic solids.In R3,a Platonic solid or regular polyhe-dron,is a polyhedron for which every face is a copy of a regular polygon,fixed over all faces,and the degree of every vertex isfixed.Let(v,e,f)denote the numbers of vertices,edges,and faces of a regu-lar polyhedron.Although there are an infinite num-ber of regular polygons,there are onlyfive regular polyhedra:tetrahedron(4,6,4),cube(8,12,6),octahe-dron(6,12,8),icosahedron(12,30,20),and dodecahe-dron(20,30,12).The notion of regular polyhedron can be generalized to higher dimensions to obtain a regular polytope.In R4,it turns out that there are six regu-lar polytopes:simplex(5,10,10,5),cube(16,32,24,8), cross polytope(8,24,32,16),24cell(24,96,96,24),120 cell(600,1200,720,120),600cell(120,720,1200,600). The forth element in each sequence denotes the num-ber of3D cells(which are regular polyhedra).Finally, in R d for any d>4,there are only three regular poly-topes:simplex,cube,and cross polytope.Wefirst address the problem of generating a uni-formly distributed set of points over S d.Consider in-scribing any(d+1)-dimensional regular polytope in-side of S d,so that all of its n vertices lie in S d.The set of vertices are beautifully arranged around S d so that the points are evenly spaced.Furthermore,the edges of the polytope yield a regular lattice structure that is natural for building roadmaps in planning problems. For the case of sampling SO(3),we simply use a set of vertices that lie in one hemisphere(making sure that no antipodal pairs of points appear in the set). The edges can be obtained directly from the polytope by making the appropriate identification of antipodal pairs.Unfortunately,there are only a few combinations of n and d,for which these ideal samples may be con-structed for S d and SO(3).This might be suitable for some applications,such as picking a set of candidate directions from S d for gradient descent of a potential function;however,in general,we would like to a have a nice distribution of points for any value of n.To the best of our knowledge,it is impossible to perfectly space n points around S d,for any n and ford>1.One simple idea that increases the numberof samples is place one point in the center of each of the c d-cells of some regular polytope,and lift it to S d.If we take the union of these points with the set of v polytope vertices,a nice point set of size c+v may be obtained.If more points are placed;however, the problem becomes more complicated.Therefore, we are willing to tolerate some distortion in the dis-tribution of points.It still seems useful,however,to borrow some of the properties of the regular polytopes to generate good samples.The general idea pursued in this paper is to sample uniformly on the surface of the regular polytope,and then transform generated distribution on the surface of the sphere.We next describe this general method and discuss the induced distortion.Consider a(d+1)-dimensional regular polytope in-scribed in the sphere S d.Suppose there exists a good method of sampling the surface of this polytope.The faces(d-dimensional cells)of the polytope,if projected outward to the surface of the sphere,form a tiling of the surface with the d-dimensional spherical polytopes.Consider some particular face,F,and its correspond-ing spherical face,F .Each point inside F can be described by the barycentric coordinate systems in-duced by vertices of F after its triangulation.Now imagine that a distribution of points is generated in-side F.Each of the points in this distribution can be obtained through several steps of linear interpola-tion between the vertices of the barycentric coordinate systems.The distribution on F can be obtained then through similar steps of interpolating between the ver-tices of F ,except that the interpolation should be done on the surface of the sphere[17].This idea is similar to the one proposed in[2]for stratified sam-pling of spherical triangles.As an example,consider a cube inscribed in the sphere S2,and sample the sur-face of the cube by putting the Sukharev grid[12,20] on each square ing the proposed method we get a distribution of samples on S2as shown on Figure 1.The distribution of points on the sphere S d ob-tained by this method will introduce distortion since spherical arcs corresponding to the intervals inside F with the same length may have different lengths in F .The amount of the distortion,and therefore bounds on the dispersion and discrepancy,can be obtained through the analysis of the maximal arc differences.This idea can also be adapted to SO(3)(and in gen-eral to the projective space of any dimension).Take a four-dimensional regular polytope inscribed in S3and use only half of the faces to generate the distribution 3on the surface.We pick the faces so that in the set of used faces,there must not exist a pair of antipo-dal points,one from each of two different faces.This way the obtained samples will cover exactly half of the sphere,which forms SO(3)surface.Next we show how to generate a layered Sukharev grid sequence on S d based on the inscribed cube and the bounds on the dispersion and the discrepancy of this sequence.4A Sample Sequence Based on CubesIn this sectionfirst we make an overview of the techniques existing for sampling unit cubes.Next we show a particular sequence adapted to the spheres us-ing the proposed general method and we analyze the uniformity properties of this sequence.4.1Sampling in CubesThe subject of uniform sampling inside unit cube [0,1]d has been studied extensively for decades(see [14,15]).Here are some brief concepts.There are two main sampling families that are con-sidered in the literature:point sets and sequences.For a point set,the number of points,n,that should be placed in the set is specified in advance,and a set of n points is chosen so that the sampling criterion (dispersion or discrepancy)is optimized.The notion of ordering between the points is not defined for the point sets.As an example we could consider the point sets generated by classical grid and Sukharev grid[20] of resolution l in[0,1]d.Each of these sets contains l points per axis and l d points total.The difference be-tween them is in the way each of these grids places its points in each of the l d subregions of the cube.Clas-sical grid places a vertex in the origin of each region, whereas Sukharev grid places a vertex at the center of each region.It was proven that the Sukharev grid optimizes the l∞dispersion over all of the point sets of size l d[15,20].Classical grid has low dispersion but is not dispersion optimal.For sequences the ordering of the points becomes important.Each next point in a sequence should be chosen so that the sampling criterion is optimized.Se-quences are particularly suitable for the motion plan-ning algorithms,where the number of points needed to solve a given problem is not known in advance.When designing sequences that optimize dispersion, it is useful to consider multiresolution grid sequences [13].A multiresolution grid of resolution l is a grid with2l points per axis and2dl points total.From thisdefinition it follows that a grid of resolution l contains all of the points from resolution l−1.The natural way to make this grid incremental is to build it one resolution at a time.During construction of the points from the same resolution level,the recursive procedure at each step adds those points that maximally decrease the discrepancy of the sequence,which extends van der Corput’s one-dimensional sequence[21].As an example,consider a square,[0,1]2,with four grid points inside.The best order of placing these points is:(0,0),(0.5,0.5),(0,0.5),(0.5,0).To add the next12points from resolution3,what point should be placedfirst,second,and third out of this sequence?The idea is that every four points should follow the same ordering of quadrants as thefirst four points(i.e.,thefirst point should fall into the left-bottom rectangle,the next into right-top,and so on).Where exactly the point should be placed within the left-bottom rectangle should be decided by the same criterion that was used to place thefirst4points.In this case the next point is(0.25,0.25).The resulting sequence has several important prop-erties:it is incremental,it has low dispersion at each resolution level,it has optimal discrepancy with re-spect to the set of canonical rectangles,it has lattice structure,and there are efficient methods for gener-ating the sequence and performing nearest neighbor queries on it[13].This makes multiresolution grid sequences particularly useful for motion planning ap-plications.We will be using a layered version of this sequence.A layered Sukharev grid of resolution l is a point setcontaining all the points of Sukharev grids of res-olutions1,2,4,...2l.It follows that this grid has n=l i=0(2i)d=(2d(l+1)−1)/(2d−1)points total.A layered Sukharev grid sequence builds oneSukharev grid of resolution2i at a time,i=1,2,....Points from each of these grids then are generated by the same procedure as for building multiresolution grid sequences.In what follows we generalize layered Sukharev grid sequence to the sphere S d.Wefirst show how the points should be generated in each of the spherical cubes,and then how all these points can be combined into one sequence on the sphere.4.2Layered Sukharev Grid Sequence fora Spherical CubeConsider a face,F,of a(d+1)-cube inscribed in a sphere S d.F is a d-dimensional cube,which in each of its corners has d edges.If we project all of these4edges onto the surface of the sphere they form arcs, which delineate a spherical d-cube,F .The lengths,α,of these arcs are equal for all edges of F.If we consider those equatorial angles that correspond to the edges coming from a common vertex of F,we can define an angular coordinate system for the spherical face F .Indeed,the coordinates(x1,x2,...x n−1)with all possible values x i∈[0,α]specify all possible points of F .The construction of the sequence,T,essentially fol-lows the construction of the layered Sukharev grid se-quence for the unit cube,except that instead of the Euclidean coordinate system we use the angular coor-dinate system defined above.To analyze the dispersion and discrepancy of this sequence we need several definitions.Define the points of the Sukharev spherical grid of resolution2l as fol-lows:P d l= i1α2l+12l+1,i2α2l+12l+1,...,i dα2l+12l+1 :i∈Z,0≤i≤2l−1Next we define the set of spherical canonical rectan-gles,which is an extension to the canonical rectangles defined in[13].Definition4.1Given positive integers d and m,let Q d m be the following family of the d-dimensional spher-ical canonical rectangles:Q d m= i1α2m,(i1+j1)α2m ×...× i dα2m,(i d+j d)α2m : i,j∈Z,0≤i≤2m−1,1≤j≤min(2m−i,2)The following results can be stated about the dis-persion and discrepancy of T.Proposition4.2The dispersion of the sequence T at the resolution level,l,isdρ(T)≤2πdn(2−1)+1Proof:The largest spherical cap which does not con-tain any of the points in T will be smaller than the spherical cap with the center at(α/2,α/2,...,α/2) and the spherical radiusπ/2l.Since2l= d n(2d−1)+1 /2we have that the dispersion is not bigger thanπ/2l=2π/ d d .Proposition4.3The relationship between the dis-crepancy of the sequence T at the resolution level,l, taken over Q d l=l m=0Q d m and the discrepancy of the optimal over Q d l sequence,T o,is:D Q d l(T)≤D Q d l(T o)+(V max−V min)Proof:The optimal sequence,T o,may place the points in some different order than T.The maximal change in discrepancy that may occur in T comparing to T o is the difference between the maximal,V max,and the minimal,V min,volumes of the spherical canonical rectangles.Therefore,D Q d l(T)≤D Q d l(T o)+(V max−V min)Proposition4.4The sequence T has the following properties:•The position of the i-th sample in the sequence Tcan be generated in O(log i)time.•For any i-th sample any of the2d nearest gridneighbors from the same layer can be found inO((log i)/d)time.Proof:For the i-th sample it takes O(log2d i)= O((log i)/d)tofind its resolution level l.Once l is found,the corresponding point in Sukharev grid of res-olution2l needs to be generated.It was proved in[13] that this takes O(log i).Therefore,the total running time for generating one point is O((log i)/d+log i)= O(log i).The layer of the i-th sample is the Sukharev grid of resolution2l.Any of the2d nearest grid neighbors from this layer can be found in O((log i)/d)using the algorithm described in[13].In our analysis we essentially ignored all of the points from the layers below the i-th sample layer, since the number of them is not significant.In prac-tice,it may be efficient to use other layers for gener-ating nearest neighbors.Better bounds on dispersion and discrepancy may also be achieved then.4.3Layered Sukharev Grid Sequence forS dNow,that we have defined a sequence for each of the spherical cubes,we need to define an ordering in which all of the points from those sequences will be placed on the surface of the sphere.One straightfor-ward way to do this is to place one point from each5of the faces’sequences at a time.The order in which each face should be considered is decided from the fol-lowing considerations.Let the union of all of the spherical canonical rect-angles determine the range space for the whole sphere. Using the criterion of optimizing the discrepancy over the range space,the ordering of thefirst2(d+1)points for the resolution level0of the sphere can be explicitly computed.Hence,from this point on we can assume that we have such an ordering.Therefore,each next set of2(d+1)points from each of the sequences should follow the same ordering,since this will minimize the discrepancy over the range space.This will guarantee that Proposition4.3holds for the generated sequence on the sphere.Our ongoing research is directed on proving that the same result holds for the larger range spaces,i.e., the ones that include combinations of the spherical rectangles from different spherical cubes.We can state the following result for the dispersion of the sequence,T s,on the sphere:Proposition4.5The dispersion of the sequence T sat the resolution level l containing n=2(d+1)·(2d(l+1)−1)/(2d−1)points isdρ(T)≤2πdn(2d−1)2(d+1)+1Proof:Applying the same argument as in the proofof Proposition4.2,and considering that now2l= d n(2d−1)/(2(d+1))+1 /2,we obtain the de-sired bound.5ExperimentsWe have implemented our algorithm in C++and applied to implementations of PRM-based planner[9] in the Motion Strategy Library.The experiments re-ported here were performed on a2Ghz Pentium IV running Linux and compiled under GNU C++.Performance results are shown in Figures2, 3. The models that we designed are allowed only to ro-tate;therefore,the configuration space is R P3.We compared the number of nodes generated by the ba-sic PRM planner using a pseudo-random sequence of quaternions[18],a pseudo-random sequence of Euler angles,and the layered Sukharev grid sequence.The results for pseudo-random quaternions and Euler an-gles sequences were averaged over50trials.When we testedthe deterministic sequence,we made sureRandom Random Layered SukharevQuaternions Euler Angles Grid Sequence 108830211067 Figure2:This problem involves moving a robot (black)from the north pole to the south pole.Mul-tiple views of the geometry of the problem are shown (obstacles are drawn in lighter shades)as well as com-parisons of the number of nodes generated by different sampling strategies.that each particular problem does not have any ad-vantage due to coincidental alignment with the grid directions of the sequence.Therefore,in each trial a fixed,random quaternion rotation was premultiplied to each sample,to displace the entire sequence.The results obtained were averaged over50trials(a differ-ent random rotation was used in each).Based on our experiments we have observed that the performance of the deterministic sequence is equiv-alent to the performance of the random sequence for the PRM-based planner,which makes it an alterna-tive approach to random sampling.It is important to note,however,that for some applications,such as veri-fication problem,only deterministic guarantees are ac-ceptable,making random sequences not appropriate.The results we obtained for the problem in Fig-ure3using Euler angles emphasizes the importance of using quaternions and sampling in a way that re-spects the Haar measure.This problem was never solved using the random Euler angles.The experiment was running for several days,generated80000nodes, 6Random Random Layered Sukharev Quaternions Euler Angles Grid Sequence 909>800001013Figure3:In this example the goal is to move a robot along the parisons of the number of nodes generated by different sampling strategies are shown.but never found the solution.It is generally known that Euler angle parameterization has its drawbacks, such as gimbal lock and interpolation problems.How-ever,in motion planning,it has been a popular way to parameterize rotations.This example demonstrates the inadequateness of Euler angles parameterization. The interpolation method,ignoring the dependence between the three rotations(yaw-pitch-roll),tries to rotate around three axes simultaneously.In the con-figuration space with the narrow corridor this results only in those configurations that are in collision.6ConclusionsWe have proposed a general framework for perform-ing deterministic uniform sampling over spheres and SO(3).We have developed and implemented a par-ticular sequence which extends the layered Sukharev grid sequence designed for the unit cube.We have tested the performance of the sequence in PRM-like motion planning algorithms,which demonstrated that this sequence is a useful alternative to a random sam-pling.This is in addition to the advantages that this sequence has over random sampling,such as deter-ministic resolution completeness guarantees and the regular lattice structure.There are many ways to improve the current work.The spherical distortion grows with the size of the polytope faces and with the dimension.One improve-ment would be to use regular polytopes that have more faces.For example,for the case of SO(3),a600-face polytope exists(only300of them would be used be-cause of antipodal identification).The difficulty is that our current approach would require sampling overa simplex,as opposed to a cube.Another possibilityis to cut and unroll the(d+1)-dimensional polytope so that all of its d-dimensional faces form a connected subset of R d.It may then be possible to adapt a sam-pling method for rectangular subsets of R d to S d by rolling the polytope back up after sampling.Another important direction of research is to de-termine how to combine deterministic sampling meth-ods for two spaces into a method over the Cartesian product space.For example,how can a sample se-quence developed for[0,1]3and another developed for SO(3)be combined to yield a good sequence for a six-dimensional configuration space that corresponds to a set of translations and rotations for a3D rigid body?In the case of random sampling,it is trivial to com-bine independent random samples;however,for deter-ministic methods,one must be very careful to avoid degeneracies.This is the reason,for example,why the Halton sequence[8]uses relatively prime integers as the basis for each dimension.Acknowledgments We are grateful for the fund-ing provided in part by NSF CAREER Award IRI-9875304,NSF ANI-0208891,and NSF IIS-0118146 The layered sequence idea was developed by Steve Lin-demann and Steve LaValle in the context of[13].References[1]N.M.Amato and Y.Wu.A randomized roadmapmethod for path and manipulation planning.In IEEEInt.Conf.Robot.&Autom.,pages113–120,1996.[2]J.Arvo.Stratified sampling of spherical triangles.In Computer Graphics(SIGGRAPH’95Proceedings),pages437–438,1995.[3]J.Barraquand and tombe.A Monte-Carlo al-gorithm for path planning with many degrees of free-dom.In IEEE Int.Conf.Robot.&Autom.,pages1712–1717,1990.[4]M.Bl¨u mlinger.Slice discrepancy and irregularitiesof distribution on spheres.Mathematika,38:105–116,1991.[5]R.Bohlin and L.Kavraki.Path planning using lazyprm.In IEEE Int.Conf.Robot.&Autom.,2000.7。
