数组元素的处理问题，大家或多或少都有听说过，例如今天要讲的就是数组元素整体移动问题。


    将数组元素整体平移，例如整体向左平移3个单位或者整体向右平移4个单位。举一个例子，现在有一个数组为[1,2,3,4,5]，整体向左平移3个单位以后得到的数组为[4,5,1,2,3]；反过来，如果将其整体向右平移4个单位，得到的新数组是[2,3,4,5,1]。这就是数组整体移动问题。



    本文我们假定整体向右平移，因为向左平移原理类似，程序稍作修改即可。

    那么对于一个长度为N的数组A，将其整体向右平移K个单位，在计算机程序设计上应该如何实现呢？



    第一种思想：新建一个数组，赋值即可

    大家可能最容易想到的一种算法就是，新建一个和数组A具有相同维度的数组B，然后从数组A的第（N-K-1）个元素（元素下标从0开始）开始赋值给数组B的第0个元素，直到数组A的末尾元素，然后回过头把A的前（N-K）个元素依次赋给数组B。这样，最终就满足了问题要求，使得B数组为A数组整体向右平移K个单位后的结果。


    算法理解清楚了，这种解决方案用程序表达出来也就很轻松了，下面就给出使用Java编写的第一种算法。这种算法的空间复杂度为O(N)，时间复杂度也为O(N)。


/**

* 最朴素的算法，开辟另一个数字，拷贝进去就是了

* @param a 输入数组

* @param k 移动步数

* 时间复杂度 O(N)

* 空间复杂度 O(N)

*/

public static void rotate1(int[] a,int k) {

int[] b = new int[a.length];

for(int i=0;i<k;i++) {

b[i]=a[a.length-k+i];

}

for(int j=0;j<a.length-k;j++) {

b[j+k]=a[j];

}

System.arraycopy(b, 0, a, 0, a.length);

}




    第二种思想：巧妙借助冒泡排序的方式

    在【AD1】中我有讲过6中经典的排序算法以及实现代码（没看过的朋友可以翻阅公众号的历史文章），其中提到了一种常见的排序算法——冒泡排序。冒泡排序的思想很简单，即两两比较，使得每次遍历数组以后都可以使得某个最大或者最小元素“浮出”数组，看起来好像鱼在水里呼吸冒泡上浮，因此叫做冒泡排序算法。那么这里，我们也可以类似思考，例如数组从[1,2,3,4,5]向右平移3个单位，变成[3,4,5,1,2]，相当于元素3,4,5依次向上冒泡，而1,2自然被沉入底部。


   这里的冒泡相比冒泡排序会更加简单，原因是冒泡排序中还要对数组的相邻元素进行比较，再确定哪个元素上浮，而这里呢，我们只用从元素3开始，两两交换使得3上浮，同时1,2整体下沉一格；然后再从元素4开始，两两交换使得4上浮，同时1,2继续整体下沉一格；最后从元素5开始，两两交换使得5上浮，同时1,2继续整体下沉至数组底部。


    下面用简洁的代码来说明上述冒泡算法。这种算法的时间复杂度为O(N*K），空间复杂度为O（1）。

/**

* 想到冒泡排序算法的思想

* @param a 输入数组

* @param k 移动步数

* 时间复杂度 O(N*k)

* 空间复杂度 O(1)

*/

public static void rotate2(int[] a,int k) {

for(int i=0;i<k;i++) {

for(int j=a.length-k+i;j>i;j--) {

int tmp=a[j];

a[j]=a[j-1];

a[j-1]=tmp;

}

}

}



    第三种思想：旋转的思维

    这种旋转思维需要我们敏锐的观察能力，如数组[1,2,3,4,5]是如何变成数组[3,4,5,1,2]的呢？从外观上来看，我们可以发现变化过程可以是这样的：



    首先将数组分成两大块，分别是[1,2]和[3,4,5]；

    然后对数组[1,2]进行颠倒，即变成了[2,1]；

然后对数组[3,4,5]也进行颠倒，即变成了[5,4,3]；

然后将两个数组拼接起来，得到[2,1,5,4,3]；

最后对上面的数组[2,1,5,4,3]进行颠倒，即可得到[3,4,5,1,2]，算法结束。



    这是一种很巧妙的算法，其时间复杂度为O（N），空间复杂度为O（1）。下面给出简洁的实现代码，对一个数组如何进行颠倒实现起来很简单，这里就不再详细说明了。


/**

* 

* @param a 输入数组

* @param k 移动步数

* 时间复杂度 O(N)

* 空间复杂度 O(1)

*/

public static void rotate3(int[] a,int k) {

reverse(a,0,a.length-k-1);

reverse(a,a.length-k,a.length-1);

reverse(a,0,a.length-1);

}

public static void reverse(int[]a,int start,int end) {

for(int i=0;i<(end-start+1)/2;i++) {

int tmp=a[start+i];

a[start+i]=a[end-i];

a[end-i]=tmp;

}

}




最后分享名句：

拥抱生活的人，生活也拥抱他。远离生活的人，生活也远离他。
 
 
 
 
 
 
来源：张泽旺 深度学习每日摘要
智造家
  查看全部

避障是指移动机器人在行走过程中，通过传感器感知到在其规划路线上存在静态或动态障碍物时，按照 一定的算法实时更新路径，绕过障碍物，最后达到目标点。

避障是指移动机器人在行走过程中，通过传感器感知到在其规划路线上存在静态或动态障碍物时，按照 一定的算法实时更新路径，绕过障碍物，最后达到目标点。

避障常用哪些传感器

不管是要进行导航规划还是避障，感知周边环境信息是第一步。就避障来说，移动机器人需要通过传感器 实时获取自身周围障碍物信息，包括尺寸、形状和位置等信息。避障使用的传感器多种多样，各有不同的原理和特点，目前常见的主要有视觉传感器、激光传感器、红外传感器、超声波传感器等。下面我简单介绍一下这几种传感器的基本工作原理。

- 超声波传感器

超声波传感器的基本原理是测量超声波的飞行时间，通过d=vt/2测量距离，其中d是距离，v是声速，t是 飞行时间。由于超声波在空气中的速度与温湿度有关，在比较精确的测量中，需把温湿度的变化和其它因素考虑进去。






上面这个图就是超声波传感器信号的一个示意。通过压电或静电变送器产生一个频率在几十kHz的超声波脉冲组成波包，系统检测高于某阈值的反向声波，检测到后使用测量到的飞行时间计算距离。超声波传感器一般作用距离较短，普通的有效探测距离都在几米，但是会有一个几十毫米左右的最小探测盲区。由于超声传感器的成本低、实现方法简单、技术成熟，是移动机器人中常用的传感器。超声波传感器也有一些缺点，首先看下面这个图。







因为声音是锥形传播的，所以我们实际测到的距离并不是 一个点，而是某个锥形角度范围内最近物体的距离。

另外，超声波的测量周期较长，比如3米左右的物体，声波传输这么远的距离需要约20ms的时间。再者，不同材料对声波的反射或者吸引是不相同的，还有多个超声传感器之间有可能会互相干扰，这都是实际应用的过程中需要考虑的。

红外传感器

一般的红外测距都是采用三角测距的原理。红外发射器按照一定角度发射红外光束，遇到物体之后，光会反向回来，检测到反射光之后，通过结构上的几何三角关系，就可以计算出物体距离D。






当D的距离足够近的时候，上图中L值会相当大，如果超过CCD的探测范围，这时，虽然物体很近，但是传感器反而看不到了。当物体距离D很大时，L值就会很小，测量量精度会变差。因此，常见的红外传感器 测量距离都比较近，小于超声波，同时远距离测量也有最小距离的限制。另外，对于透明的或者近似黑体的物体，红外传感器是无法检测距离的。但相对于超声来说，红外传感器具有更高的带宽。

激光雷达

常见的激光雷达是基于飞行时间的（ToF，time of flight），通过测量激光的飞行时间来进行测距d=ct/2，类似于前面提到的超声测距公式，其中d是距离，c是光速，t是从发射到接收的时间间隔。激光雷达包括发射器和接收器 ，发射器用激光照射目标，接收器接收反向回的光波。机械式的激光雷达包括一个带有镜子的机械机构，镜子的旋转使得光束可以覆盖 一个平面，这样我们就可以测量到一个平面上的距离信息。

对飞行时间的测量也有不同的方法，比如使用脉冲激光，然后类似前面讲的超声方案，直接测量占用的时间，但因为光速远高于声速，需要非常高精度的时间测量元件，所以非常昂贵；另一种发射调频后的连续激光波，通过测量接收到的反射波之间的差频来测量时间。






图一








图二

比较简单的方案是测量反射光的相移，传感器以已知的频率发射一定幅度的调制光，并测量发射和反向信号之间的相移，如上图一。调制信号的波长为lamda=c/f，其中c是光速，f是调制频率，测量到发射和反射光束之间的相移差theta之后，距离可由lamda * theta/4pi计算得到，如上图二。

激光雷达的测量距离可以达到几十米甚至上百米，角度分辨率高，通常可以达到零点几度，测距的精度也高。但测量距离的置信度会反比于接收信号幅度的平方，因此，黑体或者远距离的物体距离测量不会像光亮的、近距离的物体那么好的估计。并且，对于透明材料，比如玻璃，激光雷达就无能为力了。还有，由于结构的复杂、器件成本高，激光雷达的成本也很高。

一些低端的激光雷达会采用三角测距的方案进行测距。但这时它们的量程会受到限制，一般几米以内，并且精度相对低一些，但用于室内低速环境的SLAM或者在室外环境只用于避障的话，效果还是不错的。

视觉传感器

常用的计算机视觉方案也有很多种， 比如双目视觉，基于TOF的深度相机，基于结构光的深度相机等。深度相机可以同时获得RGB图和深度图，不管是基于TOF还是结构光，在室外强光环境下效果都并不太理想，因为它们都是需要主动发光的。像基于结构光的深度相机，发射出的光会生成相对随机但又固定的斑点图样，这些光斑打在物体上后，因为与摄像头距离不同，被摄像头捕捉到的位置也不相同，之后先计算拍到的图的斑点与标定的标准图案在不同位置的偏移，利用摄像头位置、传感器大小等参数就可以计算出物体与摄像头的距离。而我们目前的E巡机器人主要是工作在室外环境，主动光源会受到太阳光等条件的很大影响，所以双目视觉这种被动视觉方案更适合，因此我们采用的视觉方案是基于双目视觉的。

[20161123 03 robot06]





双目视觉的测距本质上也是三角测距法，由于两个摄像头的位置不同，就像我们人的两只眼睛一样，看到的物体不一样。两个摄像头看到的同一个点P，在成像的时候会有不同的像素位置，此时通过三角测距就可以测出这个点的距离。与结构光方法不同的是，结构光计算的点是主动发出的、已知确定的，而双目算法计算的点一般是利用算法抓取到的图像特征，如SIFT或SURF特征等，这样通过特征计算出来的是稀疏图。

要做良好的避障，稀疏图还是不太够的，我们需要获得的是稠密的点云图，整个场景的深度信息。稠密匹配的算法大致可以分为两类，局部算法和全局算法。局部算法使用像素局部的信息来计算其深度，而全局算法采用图像中的所有信息进行计算。一般来说，局部算法的速度更快，但全局算法的精度更高。

这两类各有很多种不同方式的具体算法实现。能过它们的输出我们可以估算出整个场景中的深度信息，这个深度信息可以帮助我们寻找地图场景中的可行走区域以及障碍物。整个的输出类似于激光雷达输出的3D点云图，但是相比来讲得到信息会更丰富，视觉同激光相比优点是价格低很多，缺点也比较明显，测量精度要差 一些，对计算能力的要求也高很多。当然，这个精度差是相对的，在实用的过程中是完全足够的，并且我们目前的算法在我们的平台NVIDIA TK1和TX1上是可以做到实时运行。






KITTI采集的图






实际输出的深度图，不同的颜色代表不同的距离

在实际应用的过程中，我们从摄像头读取到的是连续的视频帧流，我们还可以通过这些帧来估计场景中 目标物体的运动，给它们建立运动模型，估计和预测它们的运动方向、运动速度，这对我们实际行走、避障规划是很有用的。

以上几种是最常见的几种传感器 ，各有其优点和缺点，在真正实际应用的过程中，一般是综合配置使用多种不同的传感器 ，以最大化保证在各种不同的应用和环境条件下，机器人都能正确感知到障碍物信息。我们公司的E巡机器人的避障方案就是以双目视觉为主，再辅助以多种其他传感器，保证机器人周边360度空间立体范围内的障碍物都能被有效侦测到，保证机器人行走的安全性。

避障常用算法原理

在讲避障算法之前，我们假定机器人已经有了一个导航规划算法对自己的运动进行规划，并按照规划的路径行走。避障算法的任务就是在机器人执行正常行走任务的时候，由于传感器的输入感知到了障碍物的存在，实时地更新目标轨迹，绕过障碍物。

Bug算法

Bug算法应该是最简单的一种避障算法了，它的基本思想是在发现障碍后，围着检测到的障碍物轮廓行走，从而绕开它。Bug算法目前有很多变种， 比如Bug1算法，机器人首先完全地围绕物体，然后从距目标最短距离的点离开。Bug1算法的效率很低，但可以保证机器人达到目标。






Bug1算法示例

改进后的Bug2算法中，机器人开始时会跟踪物体的轮廓，但不会完全围绕物体一圈，当机器人可以直接移动至目标时，就可以直接从障碍分离，这样可以达到比较短的机器人行走总路径。






Bug2算法示例

除此之外，Bug算法还有很多其他的变种， 比如正切Bug算法等等。在许多简单的场景中，Bug算法是实现起来比较容易和方便的，但是它们并没有考虑到机器人的动力学等限制，因此在更复杂的实际环境中就不是那么可靠好用了。

势场法（PFM）

实际上，势场法不仅仅可以用来避障，还可以用来进行路径的规划。势场法把机器人处理在势场下的 一个点，随着势场而移动，目标表现为低谷值，即对机器人的吸引力，而障碍物扮演的势场中的一个高峰，即斥力，所有这些力迭加于机器人身上，平滑地引导机器人走向目标，同时避免碰撞已知的障碍物。当机器人移动过程中检测新的障碍物，则需要更新势场并重新规划。






上面这个图是势场比较典型的示例图，最上的图a左上角是出发点，右下角是目标点，中间三个方块是障碍物。中间的图b就是等势位图，图中的每条连续的线就代表了一个等势位的一条线，然后虚线表示的在整个势场里面所规划出来的一条路径，我们的机器人是沿着势场所指向的那个方向一直行走，可以看见它会绕过这个比较高的障碍物。最下面的图，即我们整个目标的吸引力还有我们所有障碍物产生的斥力最终形成的一个势场效果图，可以看到机器人从左上角的出发点出发，一路沿着势场下降的方向达到最终的目标点，而每个障碍物势场表现出在很高的平台，所以，它规划出来的路径是不会从这个障碍物上面走的。

一种扩展的方法在基本的势场上附加了了另外两个势场：转运势场和任务势场。它们额外考虑了由于机器人本身运动方向、运动速度等状态和障碍物之间的相互影响。

转动势场考虑了障碍与机器人的相对方位，当机器人朝着障碍物行走时，增加斥力， 而当平行于物体行走时，因为很明显并不会撞到障碍物，则减小斥力。任务势场则排除了那些根据当前机器人速度不会对近期势能造成影响的障碍，因此允许规划出 一条更为平滑的轨迹。

另外还有谐波势场法等其他改进方法。势场法在理论上有诸多局限性， 比如局部最小点问题，或者震荡性的问题，但实际应用过程中效果还是不错的，实现起来也比较容易。

向量场直方图（VFH）

它执行过程中针对移动机器人当前周边环境创建了一个基于极坐标表示的局部地图，这个局部使用栅格图的表示方法，会被最近的一些传感器数据所更新。VFH算法产生的极坐标直方图如图所示：






图中x轴是以机器人为中心感知到的障碍物的角度，y轴表示在该方向存在障碍物的概率大小p。实际应用的过程中会根据这个直方图首先辨识出允许机器人通过的足够大的所有空隙，然后对所有这些空隙计算其代价函数，最终选择具有最低代价函数的通路通过。

代价函数受三个因素影响： 目标方向、机器人当前方向、之前选择的方向，最终生成的代价是这三个因素的加权值，通过调节不同的权重可以调整机器人的选择偏好。VFH算法也有其他的扩展和改进，比如在VFH+算法中，就考虑了机器人运动学的限制。由于实际底层运动结构的不同，机器的实际运动能力是受限的，比如汽车结构，就不能随心所欲地原地转向等。VFH+算法会考虑障碍物对机器人实际运动能力下轨迹的阻挡效应，屏蔽掉那些虽然没有被障碍物占据但由于其阻挡实际无法达到的运动轨迹。我们的E巡机器人采用的是两轮差动驱动的运动形式，运动非常灵活，实际应用较少受到这些因素的影响。

具体可以看 一下这个图示：






类似这样传统的避障方法还有很多，除此之外，还有许多其他的智能避障技术，比如神经网络、模糊逻辑等。

神经网络方法对机器人从初始位置到目标位置的整个行走路径进行训练建模，应用的时候，神经网络的输 入为之前机器人的位姿和速度以及传感器的输 入，输出期望的下一目标或运动方向。

模糊逻辑方法核心是模糊控制器，需要将专家的知识或操作人员的经验写成多条模糊逻辑语句，以此控制机器人的避障过程。 比如这样的模糊逻辑：第一条，若右前方较远处检测到障碍物，则稍向左转；第 二条，若右前方较近处检测到障碍物，则减速并向左转更多角度；等等。

避障过程中存在哪些问题

- 传感器失效

从原理上来讲，没有哪个传感器是完美的，比方说机器人面前是一块完全透明的玻璃，那么采用红外、激光雷达或视觉的方案，就可能因为这个光线直接穿过玻璃导致检测失败，这时候就需要超声波这样的传感器来进行障碍物的侦测。所以我们在真正应用的过程中，肯定都需要采取多种传感器的结合，对不同传感器采集到的数据进行一个交叉验证，以及信息的融合，保证机器人能够稳定可靠的工作。

除此之外也有其他模式可能导致传感器失效，比如超声波测距，一般需要超声阵列，而阵列之间的传感器如果同时工作的话，会容易互相产生干扰，传感器A发射的光波反射回来被传感器B接收，导致测量结果出现错误，但是如果按照顺序一个个工作，由于超声波传感器采样的周期相对比较长，会减慢整个采集的速度，对实时避障造成影响，这就要求从硬件的结构到算法都必须设计好，尽可能提高采样速度，减少传感器之间的串扰。

还有比如说，机器人如果需要运动的话，一般都需要电机和驱动器，它们在工作过程中都会产生电容兼容性的问题，有可能会导致传感器采集出现错误，尤其是模拟的传感器，所以在实现过程中要把电机驱动器等设备、传感器的采集部分，以及电源通信部分保持隔离，保证整个系统是能够正常工作的。

- 算法设计

在刚刚提到的几个算法，很多在设计的时候都并没有完善考虑到整个移动机器人本身运动学模型和动力学模型，这样的算法规划出来的轨迹有可能在运动学上是实现不了的，有可能在运动学上可以实现，但是控制起来非常困难，比如刚刚提到的如果一台机器人的底盘是汽车的结构，就不能随心所欲地原地转向，或者哪怕这个机器人是可以原地转向，但是如果一下子做一个很大的机动的话，我们的整个电机是执行不出来的。所以在设计的时候，就要优化好机器人本身的结构和控制，设计避障方案的时候，也要考虑到可行性的问题。

然后在整个算法的架构设计的时候，我们要考虑到为了避让或者是避免伤人或者伤了机器人本身，在执行工作的时候，避障是优先级比较高的任务，甚至是最高的任务，并且自身运行的优先级最高，对机器人的控制优先级也要最高，同时这个算法实现起来速度要足够快，这样才能满足我们实时性的要求。

总之，在我看来，避障在某种程度上可以看做机器人在自主导航规划的一种特殊情况，相比整体全局的导航，它对实时性和可靠性的要求更高一些，然后，局部性和动态性是它的一个特点，这是我们在设计整个机器人硬件软件架构时一定要注意的。

多机协同的避障策略有哪些？

多机协同避障策略在整个SLAM方向上都还是一个在钻研的热点领域，单纯就避障来说，目前的方案是，当有两个或多个机器人协同工作的时候，每个机器人会在一个局部各自维护一个相对的动态地图，所有机器人共享一个相对静态的地图，而对于单个机器人来说，它们会各自维护一个更加动态的地图，这样当两个机器人接近一个位置时，它们会将它们维护的动态地图合并起来。

这样子有什么好处呢，比如视觉只能看到前方一个方向，这时候跟后面机器人的动态地图合并之后，就能看到前后整个局部的动态信息，然后完成避障。

多机协同的关键在于，两个局部地图之间的分享，就是它们分别在整个相对静态的全局地图上是有一小块一个窗口的位置，到这两个窗口可能融合的话，会把它们融合在一起，同时去指导两个机器人的避障。在具体实现过程中，也要考虑整个信息传输的问题，如果是自己本身的局部地图，由于都是本机的运算，速度一般都比较快，如果是两个机器人协作的话，就要考虑到传输的延时，以及带宽的问题。

避障有无标准的测试标准和指标？

目前就我所了解业界并没有什么统一的测试标准和指标，我们目前测试的时候会考虑这些指标，比如在单个障碍物或是多个障碍物，障碍物是静态的或动态的情况下避障效果如何，以及实际规划出的路径完美度如何，还有这个轨迹是否平滑，符合我们观感的效果。

当然，这个最重要的指标我觉得应该避障是否失败就是成功率的问题，要保证这个避障不管是碰到静态的或者是动态的物体，然后那个物体不管是什么材质，比如说如果是动态的人，我们穿什么样的衣服会不会对整个避障功能造成影响，另外就是不同的环境又会有什么样的影响，比如光线充足或暗淡。对于避障来说，成功率才是最为关键的。
 
 
来源：网络 查看全部

为减小对工业机械臂振动和机构磨损，提高机械臂轨迹跟踪精度，在关节空间分别研究了通过
起点和终点的三次、五次和七次多项式轨迹算法，以及途经2、4个中间点的4．3_4、3—5—3、3．3—3．3—3多
项式轨迹插补算法。在此基础上，给出了贯穿N路径点的机械臂连续三次样条轨迹快速迭代算法。
试验表明：机械臂途经期望的N-2(Ni>4)中间点时，充分满足轨迹给定的约束条件，保证关节位置、
速度轨迹连续可导和加速度轨迹的连续性，可进一步提高关节轨迹的平滑性，减少额外游移运动，提
高高精度平稳控制。




链接：http://pan.baidu.com/s/1dENLptR 密码：e0nt 查看全部

　以前的一系列文章，都在说明APS会是工业4.0落地的关键解决方案。而在前天的文章【原创干货】APS基础知识　介绍的最基本的APS的最关键的算法（前天的文章题目其实叫APS基础算法更贴切）。前天介绍的算法中，最核心的是计算EPST和LPST。而其中EPST是根据前向算法计算的，LPST是根据后向算法计算的。可以排程的基本条件是每个订单的EPST都不迟于LPST。但是EPST和LPST是如何计算的呢？

LPST算法：

一般产品的生产提前期包括：产线切换时间、生产时间、等待时间。LPST算法根据交付期，减去等待时间、生产实践，切换时间，就是这个订单最迟的计划开始时间。如图：






EPST算法EPST有几个规则：

１、不能早于计划员计划的时间。

２、生产资源（包括设备、员工）可提供的时间。

３、生产资料的可提供时间。

算法如图






这个逻辑看似非常简单，但这里面有一个嵌套：如果一个产品，需要多个部件，而这些部件也是工厂生产的。那么这个产品的订单会分解为多个制造订单。

最终的组装工单。

部件的生产工单。

这个过程需要展BOM计算。

部件的生产工单的LPST，需要通过组装的LPST计算。

组装工序的EPST，需要通过部件工序的EPST计算。

部件工序、组装工序的LPST，EPST相互影响。这是APS算法复杂的原因之一。

APS算法还有其他的复杂因素：

１、当存在瓶颈资源时，订单的优先排序的规则。

２、排产时，订单还有备选的生产资源，在生产资源之间还需要选择。

３、在计算EPST时，对生产原材料的选择（现有库存、运输在途，在制品，或者备选其他的可替代部件）。

这些都是APS算法复杂的原因。

但是人处理问题的时候，喜欢把所有问题同时解决。而计算机处理复杂问题的时候，更容易通过简单的规则的反复迭代获得好的解决方案。

而APS是计算机解决复杂问题的一套算法，最好的APS解决方案，一定是解耦的（减少关联关系）；简单的：简单规则反复迭代；灵活的：一些规则可定义的。

国内很多APS研究者，喜欢研究各种APS的算法，其实越简单的算法，在计算机处理领域应用越广。
 
来源： 微信原创作者 许永硕 查看全部