UP | HOME

Read Scientific Documents

Table of Contents

Planning Algorithm

Introduction

为什么要学习规划算法?

  1. 使用机器解决甚至是人类很难解决的问题;
  2. 已经在工业界和学术界取得成功,包括:机器人、制造、药物设计和航空。

简单说就是规划算法应用非常广泛,能够解决很多的问题(很多问题可以看作 规划问题)。

典型的规划问题包括:

  • Discrete Puzzle/scheduling
  • A motion planning puzzle: Alpha 1.0 puzzle
  • An automotive assembly task
  • Sealing cracks in automotive assembly
  • Piano Mover’s Problem
  • Navigating mobile robots
  • Playing hide and seek
  • Making smart video game characters
  • Virtual humans and humanoid robots
  • Parking cars and trailers
  • “Wreckless” driving
  • Flying Through the Air or in Space
  • Designing better drugs

可以看作一样的术语有:

  • robot, agent, controller
  • action, operator

规划的基本要素

  • 状态
  • 时间
  • 动作
  • 初始和目标状态
  • 标准:
  • 可行性(已很有挑战性)(幸运的是和最优解接近)
  • 最优性(大部分问题很难)

Problem Formulation

  • 状态转移方程 \(x=f(x,u)\)
  • 可能的动作 \(U=\cup_{x\in{}X}U(x)\)

离散可行性规划

  1. 非空的 状态集合 X, 是有限的或者可数无限的状态集合。
  2. 对于每个状态\(x\in{}X\),有一个有限的 *动作空间

$U(x)$。 3. *状态转移方程f

  • 初始状态 \(x_I\in{}X\)
  • 目标集合 \(X_G\in{}X\)
  • Logic-based

    优点:

    • 压缩,用01010101字符串表示
    • 用户容易理解

    缺点:

    • 很难生成
    • 不能处理连续空间、不可预知、感知不确定、多决策生成

    几何建模

    常用的两种表示方法:

    • boundary representation: equation
    • solid representation: the set of all points
    • 多边形和多面体模型
      • 多边形
        • 半平面 $ Hi = \{(x,y) ∈ \mathcal{W} | fi(x,y) \leq 0 \} $
        • 凸多边形 $ \mathcal{O}=H1 ∩ H2 ∩ \cdots ∩ Hm$ 令$e(x,y)$在$f(x,y) \leq 0$的时候返 回TRUE,否则返回FALSE,则凸多边形可以用逻辑与来表 示:\(\alpha(x,y)=e_1(x,y) \wedge e_2(x,y) \wedge \cdots \wedge e_m(x,y)\)
        • 凹多边形 $ \mathcal{O}=\mathcal{O}1 ∪ \mathcal{O}2 ∪ \cdots ∪ \mathcal{O}n $,用逻辑或表示 为:$φ=α1(x,y) ∨ α2(x,y) ∨ \cdots ∨ αn(x,y) $
      • 多面体
        • \(H_i=\{(x,y,z) \in \mathcal{W} | f_i(x,y,z) \leq 0\}\)

        类人机器人两脚同时着地的时候是 closed kinematic chains

    构型空间 (The Configuration Space)

    拓扑

    如果 \(X\) 是一个 开集合(open sets) ,集合 \(X\) 可以称为 拓扑空间 (topological space) ,具有以下公理:

    1. 可数个开集合的合集是开集合 (指不包含边界的集合)
    2. 有限数个开集合的交集是开集合
    3. \(X\) 和 \(\Phi\) 都是开集合
    • Hausdorff 公理
      任意不相同的\(x_1, x_2 \in X\),存在开集合 \(O_1\) 和 \(O_2\) 使得 \(x_1 \in O_1, x_2 \in O_2 \text{且} O_1 \cap O_2 = \Phi\)
    • Homeomorphism:拓扑等价
      假设$f : X ↔ Y$是拓扑空间X和Y之间的双端映射,如果 \(f\) 和 \(f^{-1}\) 都是连续的,则 \(f\) 为拓扑等价,表示为 \(X \cong Y\)
    • Manifolds
      • 定义
        拓扑空间$M \subseteq \mathbb{R}m$是manifold,如果对于所有的 $x ∈ M$,存在开集合 \(O \subset M\) 使得:
        1. \(x \in O\)
        2. \(O\) 拓扑等价于 \(\mathbb{R}^n\)
        3. \(n\) 对于所有的 \(x \in M\) 是固定

        的, \(n\) 被称为manifold的维数。


      1. \(\text{int}(U)\) 表示 \(U\) 的 *内点(interior point)*,定义为 \(x ORG-LIST-END-MARKER \in O_1 \text{且} O_1 \subseteq U\)
        1. 外点(exterior point) : \(x \in O_2 \text{且} O_2 \subseteq X ORG-LIST-END-MARKER \backslash U\)
          1. \(\partial U\) 表示 \(U\) 的 边界
          2. 闭集(closure) 定义为 \(\text{cl}(U)=\text{U} \cup \partial U\)

    The Piano Mover’s Problem (Formulation)

    1. 世界 \(\mathcal{W}=\mathbb{R}^2\) 或者 \(\mathcal{W}=\mathbb{R}^3\)
    2. 障碍区域 \(\mathcal{O} \subset \mathcal{W}\)
    3. 机器人 \(\mathcal{A}\) 或者 \(\mathcal{A}_1,\mathcal{A}_2,\dots,\mathcal{A}_m\)
    4. 结构化空间 \(\mathcal{C}=\mathcal{C}_{obs} \cup \mathcal{C}_{free}\)
    5. 初始点 \(q_I \in \mathcal{C}_{free}\)
    6. 目标点 \(q_G \in \mathcal{C}_{free}\)
    7. 路径 \(\tau : [0,1] \to \mathcal{C}_{free}\) ,其中 \(\tau(0)=q_I\) , \(\tau(1)=q_G\)

    2维刚体:\(SE(2)\)

    \(\mathcal{C}=M_1 \times M_2 = \mathbb{R}^2 \times \mathbb{S}^1\)

    3维刚体:\(SE(3)\)

    \(\mathcal{C}=\mathbb{R}^3 \times \mathbb{R}\mathbb{P}^3\)

    • 四元数
      \(h \in \mathbb{H}\) 表示为 \(h=a+bi+cj+dk\) ,其中 \(a,b,c,d \in \mathbb{R}\) , \(i^2=j^2=k^2=ijk=-1\) , \(ij=k,jk=i,ki=j\)
      • 乘法
        \( \begin{eqnarray*} h_1 & = & a_1 + b_1i + c_1j + d_1k \\ h_2 & = & a_2 + b_2i + c_2j + d_2k \\ h_1 \cdot h_2 & = & a_3 + b_3i + c_3j + d_3k \\ a_3 & = & a_1a_2 - b_1b_2 - c_1c_2 - d_1d_2 \\ b_3 & = & a_1b_2 + a_2b_1 + c_1d_2 - c_2d_1 \\ c_3 & = & a_1c_2 + a_2c_1 + b_2d_1 - b_1d_2 \\ d_3 & = & a_2d_2 + a_2d_1 + b_1c_2 - b_2c_1 \end{eqnarray*} \) 令 \(v=[b \quad c \quad d]\) ,则 \( h_1 \cdot h_2 = \left[ \begin{array}{l} a_1a_2 - v_1 \cdot v_2 \\ a_1v_2 + a_2v_1 + v_1 \times v_2 \end{array} \right] \) 旋转矩阵 \( R(h) = \left( \begin{array}{lll} 2(a^2+b^2)-1 & 2(bc-ad) & 2(bd+ac) \\ 2(bc+ad) & 2(a^2+c^2) - 1 & 2(cd-ab) \\ 2(bd-ac) & 2(cd+ab) & 2(a^2+d^2) - 1 \end{array} \right) \) 根据旋转矩阵求四元数: $a=\frac{1}{2}\sqrt{r11+r22+r33+1}$, 当 $a ≠ 0$, \( \begin{eqnarray*} b & = & \frac{r_{32}-r_{23}}{4a} \\ c & = & \frac{r_{13}-r_{31}}{4a} \\ d & = & \frac{r_{21}-r_{12}}{4a} \end{eqnarray*} \) 否则 \( \def\fengmu{\sqrt{r^2_{12}r^2_{13}+r^2_{12}r^2_{23}+r^2_{13}r^2_{23}}} \begin{eqnarray*} b & = & \frac{r_{13}r_{12}}{\fengmu} \\ c & = & \frac{r_{12}r_{23}}{\fengmu} \\ d & = & \frac{r_{13}r_{23}}{\fengmu} \end{eqnarray*} \)

    Motion

    Online ZMP Sampling Search for Biped Walking Planning

    consider walk planning as the choice of a sequence of ZMPs leading to a stable walk that satisfies all the dynamic and mechanical constraints of the robot.

    online sampling algorithm

    use a rectangle as the reachable area of CoM

    Input: footstep plan, initial CoM

    use CoM to control ZMP (by searching)

    Dynamically-stable Motion Planning for Humanoid Robots

    implementing a practical complete planner is a daunting task for even low-dimensional configuration spaces

    collision-free

    Provided the initial and goal configurations correspond to statically-stable body postures, the path returned by the planner can be transformed into a collision-free and dynamically-stable trajectory for the entire body.

    Dynamically Stepping Over Obstacles by the Humanoid Robot HRP-2

    Foot Trajectory Planning: Clamped Cubic Splines

    Motion Planning for Walking Pattern Generation of Humanoid Robots

    plan the collision free motion for walking pattern generation of a humanoid robot

    plan the motion with keeping the horizontal position of the COG as well as the position/orientation of the feet/hand.

    generating a walking pattern of a humanoid robot with- out causing unnecessary collision among the links and the environments.

    Combining Key Frame based Motion Design with Controlled Movement Execution

    To satisfy the condition of a quasi static motion, the acceleration must be bounded all the time

    While using this key frame approach to control the motion of the limbs, the orientation of the body in space, and the height of the CoM over the ground, the feedback controller presented in section 3.1 generates a motion trajectory for the horizontal components of the robot’s CoM position ensuring the stability of the motion.

    Whole body posture controller based on inertial forces

    treat different humanoid locomotion modes (walking, running, etc.) with a unified approach.

    华山论剑 ——《学术会议高手速成 之 七种武器》读后感 2009-08-26

    不久之前在网上偶然看到《学术会议高手速成 之 七种武器》,觉得非常经 典,今天又翻出来读一读,温故而知新。文章以诙谐的手法,把 学术界 比 作是 江湖*;而 *学术会议 则是 华山论剑*。要想混迹于江湖,华山论剑 是少不了的;但是 *学术江湖,虽无刀光剑影,却有血雨腥风。 对于我这种 初入江湖的晚辈来说,榕二前辈在文中给出在学术会议上常用的七种武器非常 实用。虽然题目讲速成,但是要想掌握这七种武器并不容易;特别是最后两种 武器,不仅要练习招式,更要修心才能练成。文中的七种武器可以归纳为下表 (原文非常生动有趣):

    等级武器诀窍起手式
    1长生剑微笑“我对这个领域不太了解,但是我很好奇……”,“也许前辈已经提到了但是我没听懂,这个……”,“或许这是个很笨的问题,但是我真的很想知道……”
    2孔雀翎信心“这是个非常好的问题!非常好的问题通常都不会有非常简单的答案。我会从下面三个角度来回答……”
    3碧玉刀包装穿着正式,提问
    4多情环政治煽情、社交、探讨、移情、仇恨、执着
    5离别钩不按套路出牌让对手和他们熟悉的领域分离,让话题与自己熟悉的领域相聚。
    6霸王枪Don’t get mad; don’t get even; get ahead自强、自知、坦荡、无悔、无畏
    7拳头Are you happy?

    可以看出,越是高等级的武器对于练习者的“内功”要求越高,没有武器才是 最高境界。 *这个世界上远不止七种武器,你穷尽一生也无法精通每一种兵器。

    • *但是你的微笑,你的勇气,你的信心,你的诚实,你的仇恨,你的骄傲,你

    的勇气还有爱,任何人都拿不走。当你真正掌握了这些真正的武器,这才是真 正的手中无剑心中也无剑,这才是真正的无招胜有招。* 这时候才能算是笑傲 江湖。

    而文章最后"鼓励大家用爱来对待自己的人生和所选择的科研事业的同时,也 希望同学们用一个科研工作者严谨谦卑理性思辨的态度来对待你的爱。" 但是,

    什么是爱呢?

    问世间,情为何物,教人生死相许?

    作为一名学术界治学严谨的科学工作者,我们应该如何研究‘爱’这种神秘的 物质呢?

    虽然文中没有直接给出答案,但是榕二前辈的导师和老板给出了一个测试标准: Are you happy? 这个的问题值得我经常地问自己,因为" 如果你真正热爱你所做的工作,你就会对你的工作朝思暮想牵肠挂肚,你就会在从事工作的时候充满激情感到快乐,这样没有什么能够阻挡你前进的步伐,这样你才能成为 高手中的高手。 " 我的答案是: Yes, I'm happy.

    高效地阅读科技论文

    准备

    • 找个安静的地方
    • 论文、笔和纸

    确定阅读内容

    • 读标题和摘要
    • 继续读?

    泛读

    • 他们做了什么?
    • 浏览简介、标题、图片、定义、结论和参考文献
    • 可信度如何?
    • 有实用价值吗?
    • 继续?

    精读

    • 他们怎么做的?
    • 质疑文章的内容
      • 检查假设
      • 检查方法
      • 检查数据统计
      • 检查推理和结论
    • 怎样将他们的方法为自己所用?

    做笔记

    • 边读边做笔记
    • 标出关键点
    • 标出新的术语和定义
    • 图、表
    • 写总结

    How To Review A Paper

    Being invited to review a manuscript by editor from Int. J. Humanoid Robotics, is a honor.

    • What constitutes a good review and reviewer?
    • How should the review of a manuscript be approached?
    • What elements of a review are most useful to the authors and editors?
    • Should a manuscript be reviewed differently depending on the nature of the journal?
    • The purpose of peer review is to ensure
      1. quality, checking that no mistakes in procedure or logic have been made;
      2. that the results presented support the conclusion drawn;
      3. that no errors in citations to previous work have been made;
      4. that all human and animal protocols conducted follow proper review and approval by appropriate institutional review committees;
      5. that the work is **original** and **significant**.
    • Elements of manuscript review
      • technical
      • ethical
    • Criteria for manuscript review
      1. Scientific quality of the work
        • Are the methods appropriate and presented in sufficient detail to allow the results to be repeated?
        • Are the data adequate to support the conclusions?
      2. Presentations
        • Writing: Is it clear, concise, and in good English?
        • Title: Is it specific and does it reflect the content of the manuscript?
        • Abstract: Is it brief and does it indicate the purpose of the work, what was done, what was found, and the significance?
        • Figures: Are they justified? Are they sharp, with lettering proportionate to the size of the figure? Are there legends to explain the figures?
        • Tables: Can they be simplified or condensed? Should any be omitted?
        • Trade names, abbreviations, symbols: Are these misused?
      3. Research violations
        • Are there violations of the Guiding Principles in the Care and Use of Laboratory Animals?
        • If the research involved human subjects, were the studies performed in accordance with the Declaration of Helsinki?
      4. Rating
        • Assign a rating on the reviewer form; rank the manuscript relative to other work in the same field.
      5. Confidential comments
        • Provide comments regarding the novelty and significance of the manuscript.
        • Provide a recommendation about the manuscript’s suitability for publication in the journal; these comments will not be returned to the author(s).
      6. Comments for authors
        • On the reviewer form, provide specific comments, preferably numbered, on the design, presentation of data, results, and discussion. DO NOT include recommendations for publication on the second page.
        • Please be certain that your comments to the author(s) are consistent with your rating recommendation.
      7. Privileged document
        • This manuscript is a privileged communication; the data and findings are the exclusive property of the author(s) and should not be disclosed to others who might use this information in their research.
        • The manuscript, illustrations, and tables should be destroyed upon completing the review or, if anticipating a revision, kept confidential until the review process is complete.
        • If you have shared responsibility for the review of this manuscript with a colleague, please provide that person’s name and institutional affiliation.
    • Reviewer's etiquettte and responsibilities
      • **golden rule**: treat allmanuscripts in the same manner that you would want your own treated.
    • Checklist for reviews: issues for comment
      1. Importance of research question
      2. Originality of work
      3. Delineation of strengths and weaknesses of methodology/experimental/statistical approach/interpretation of results
      4. Writing style and figure/table presentation
      5. Ethical concerns (animal/human)
    • A SYSTEMATIC GUIDE TO REVIEWING A MANUSCRIPT
      • Before Writing the Review
        • To which manuscript category does this manuscript best conform?
        • Are there any potential biases in reviewing this manuscript?
        • Does the manuscript address an important problem?
        • Has the manuscript been previously published?
      • The Abstract
        • Does the Abstract appropriately summarize the manuscript?
        • Are there discrepancies between the Abstract and the remainder of

    the manuscript?

    • Can the Abstract be understood without reading the manuscript?
    • The Introduction
      • Is the Introduction concise?
      • Is the purpose of the study clearly defined?
      • Do the authors provide a rationale for performing the study based on a review of the literature? If so, is it of the appropriate length?
      • Do the authors define terms used in the remainder of the manuscript?
      • If this manuscript is Original Research, is there a welldefined hypothesis?
    • The Methods Section
      • Could another investigator reproduce the study using the methods as outlined or are the methods unclear?
      • Do the authors justify any choices available to them in their study design (e.g., choices of imaging techniques, analytic tools, or statistical methods)?
      • Do the authors justify any choices available to them in their study design (e.g., choices of imaging techniques, analytic tools, or statistical methods)?
    • The Results Section
      • Are the results clearly explained?
      • Does the order of presentation of the results parallel the order of presentation of the methods?
      • Are the results reasonable and expected, or are they unexpected?
      • Are there results that are introduced that are not preceded by an appropriate discussion in the Methods section?
    • The Discussion Section
      • Is the discussion concise? If not, how should it be shortened?
      • If a hypothesis was proposed, do the authors state whether it was verified or falsified? Alternatively, if no hypothesis was proposed, do the authors state whether their research question was answered?
      • Are the authors’ conclusions justified by the results found in the study?
      • If there are unexpected results, do the authors adequately account for them?
      • Do the authors note limitations of the study? Are there additional limitations that should be noted?
    • Figures and Graphs
      • Are the figures and graphs appropriate and are they appropriately labeled? Would a different figure better illustrate the findings?
      • Do the figures and graphs adequately show the important results?
      • Do arrows need to be added to depict important or subtle findings?
      • Do the figure legends provide a clear explanation that allows the figures and graphs to be understood without referring to the remainder of the manuscript?
    • Tables
      • If there are tables, do they appropriately describe the results? Should one or more tables be added?
    • The References Section
      • Does the reference list follow the format for the journal?
      • Does the reference list contain errors?
      • Have the authors appropriately represented the salient points in the articles in the reference list? Alternatively, have the authors misquoted the references?
      • Are there important references that are not mentioned that should be noted?
      • Are there more references than are necessary?

    © 2012-05-17 22:26:43 CEST Xu Yuan (xuyuan.cn@gmail.com) Proudly powered by Org version 7.8.10 with Emacs version 24. Validate XHTML 1.0