Stanford's Pavone Deploys Unicycle Models to Cut Trajectory Compute

斯坦福大学Pavone采用单车模型降低轨迹计算量 由于完整的动力学系统会导致实时轨迹优化在计算上难以实现，自动驾驶车辆依赖低维非完整运动学模型。 Marco Pavone教授在课程开篇区分了传统自动化与真正自主性，并概述了涵盖运动规划、感知、定位和决策的“感知-思考-行动”（See-Think-Act）自主系统栈。技术讨论随后转向移动机器人运动学，对比了完整位置约束与以普法夫形式（Pfaffian form）表示的非完整速度约束。利用线性代数以及对无滑动条件的零空间分析，Pavone推导出了经典的单车运动学模型，并论证了其在数学上与实体差速驱动机器人的等价性。最后，他探讨了类车运动学变体（Dubins和Reeds-Shepp），并解释了在连接运动学与动力学时，模型保真度与计算可行性之间的工程权衡。 斯坦福大学的机器人自主性课程分为两个季度的序列：AA274A涵盖经典自主架构，而AA274B则探讨基于学习的控制、验证、人机交互以及移动操作。 (14:43) 运动学建模突出了完整约束与非完整普法夫约束之间的根本区别：前者将可达位形空间限制在更低维的流形上，而后者在不限制位形可达性的情况下限制瞬时速度。 (32:05) 轮式移动机器人的容许速度是通过系统地寻找堆叠普法夫约束矩阵零空间的基向量推导出来的，从而直接得出控制仿射运动学运动方程。 (50:19) 差速驱动机器人在运动学上等价于单车模型，因为冗余的后轴约束和无约束的万向轮允许高层规划器在单车坐标系中生成路径，然后再将其映射到轮速上。 (62:30)

Professor Marco Pavone frames robotic autonomy as dynamic reasoning under uncertainty, contrasting it with deterministic automation and showing how modular 'See-Think-Act' systems rely on kinematic models to plan realizable physical motions. Autonomy Stack Architecture and Hardware Realities (0:05) Pavone establishes a fundamental distinction between classical automation and autonomy. While automation executes deterministic, pre-planned tasks in structured settings—such as factory arms assembling automobiles—autonomy requires machines to reason and act in open, unpredictable environments where edge cases cannot be anticipated at design time. Autonomous agents operate via the See-Think-Act cycle, a modular pipeline cycling from sensor perception and simultaneous localization and mapping (SLAM) to high-level decision making and trajectory optimization. Mastering this architecture requires bridging theoretical mathematical models with physical implementation. In Stanford's AA274A, the stack is deployed incrementally using the Robot Operating System (ROS) onto differential drive ground robots equipped with laser sensors, cameras, and onboard processors. Pavone cautions that physical robotics inevitably entails messy hardware debugging and troubleshooting, warning students that dealing with hardware frustration is an inherent component of the discipline. Holonomic Reductions Versus Nonholonomic Velocity Restrictions (32:05) A mobile robot's configuration is defined by generalized coordinates representing its pose. Mechanical linkages impose constraints that split into two primary mathematical categories: holonomic and nonholonomic. Holonomic constraints are purely algebraic functions of configuration coordinates, such as the pin joints in multi-link robotic manipulators. These constraints eliminate degrees of freedom and permanently confine the robot's accessible positions to a lower-dimensional manifold. In contrast, mobile robots are primarily governed by kinematic constraints expressed in Pfaffian form, which depend linearly on generalized velocities. When these constraints cannot be integrated back into algebraic position functions, they are classified as nonholonomic. A nonholonomic constraint restricts instantaneous velocity directions—such as preventing an automobile from sliding sideways—without restricting the accessible configuration space. Pavone illustrates that by concatenating forward, backward, and steering maneuvers, a vehicle can still achieve any desired position and heading in the planar configuration space. Null-Space Kinematics and Differential Drive Equivalence (53:35) For wheeled robots, the pure rolling without slipping condition enforces that the contact point has zero lateral velocity. Formulated mathematically, all admissible generalized velocities must lie within the null space of the Pfaffian constraint matrix. For an idealized unicycle disk rolling vertically on a plane, this kernel yields two degrees of instantaneous motion, defining the standard unicycle kinematic equations parameterized by forward linear velocity and angular rotational speed. While an isolated unicycle is statically unstable, physical platforms resolve this using a differential drive design featuring two independently driven wheels on a common axle and a passive caster wheel. Because both drive wheels share a rigid axle, their lateral no-slip conditions are mathematically redundant, and the freely pivoting caster adds no nonholonomic constraints. Pavone demonstrates that the differential drive platform is kinematically equivalent to the unicycle model: forward speed corresponds to the average of the two wheel speeds, and angular velocity is governed by their difference divided by the axle track width, allowing trajectory planners to optimize unicycle trajectories before mapping them directly to physical wheel actuators. Kinematic Simplicity Versus Trajectory Realizability (72:31) When steering mechanisms are introduced—as in the simple car, Reeds-Shepp, or Dubins models—kinematics must account for bounded steering angles and restricted drive directions. In all these platforms, kinematic models represent simplified subsystems rather than complete representations of physical dynamics. Pavone emphasizes that roboticists deliberately plan trajectories using kinematic models because their low dimensionality makes trajectory optimization computationally tractable. This abstraction introduces an essential engineering compromise between model fidelity and computational feasibility. If a planning model is overly complex, real-time optimization becomes intractable; if it is excessively simplified, the planned trajectories cannot be physically realized. Roboticists navigate this tension either by adding integrators to elevate velocity or steering rates into state variables, or by deploying low-level feedback controllers that translate kinematic commands into the motor torques and accelerations needed to execute motions on physical hardware. Kinematic models provide the mathematical foundation for mobile autonomy by defining admissible velocities under physical nonholonomic constraints, but successful real-world deployment requires balancing these low-dimensional abstractions against computational limits, actuator saturation, and lower-level dynamic control.

[8:02] Prof. Marco Pavone: Frustration is in the DNA of every roboticist [12:08] Prof. Marco Pavone: So they're going to be your best friends for this quarter [14:43] Prof. Marco Pavone: the way the registrar office works is still a little bit mystery to me... Why is that in that way that is beyond my knowledge [20:38] Prof. Marco Pavone: you cannot move sideways [20:38] Prof. Marco Pavone: by being clever in how you concatenate your backward and forward maneuver, you can go anywhere you want [20:38] Prof. Marco Pavone: assume that we are in a world where a wheel can stay perfectly in balance. [27:47] Student: Seems like you're gonna integrate that function... Unless the function is very weird, most nice functions are integrable, right? [32:05] Prof. Marco Pavone: With nonholonomic constraints you constrain the velocities but not the accessible portion of the configuration space. With holonomic constraints you constrain the accessible portion of the accessible space. [72:31] Prof. Marco Pavone: On the one hand, you want to have a model that is representative enough of the dynamics so that when you plan a trajectory, the trajectory is realizable. On the other hand, you don't want to have a model that is too complicated because trajectory optimization, as we will see next week, is a computationally intensive process.

[0:05] All right. So, welcome to principal [0:08] robot autonomy one also known as AA274A [0:13] and a number of uh other course uh [0:16] numbers. In particular, this course is [0:18] cross listed with electrical engineering [0:20] and computer science. So in this class [0:23] you will learn in a nutshell how to [0:26] endow a robot with the capability of [0:28] reasoning about the environment and [0:31] based on that reasoning uh carry out [0:34] meaningful uh actions. In particular the [0:38] goal of this class is triple. First of [0:41] all you will gain a fund fundamental [0:44] knowledge about the autonomy tech. [0:48] basically all the capabilities that [0:51] allow a robot to uh reasonable [0:53] environment and [0:56] make actions. You'll be able to uh apply [1:00] such knowledge to a number of different [1:03] domains. Uh and in particular, you will [1:06] learn not only the mathematical [1:08] underpinnings of the science of autonomy [1:11] but also the p practical aspects of the [1:13] science of autonomy. meaning that you [1:15] will learn the mathematics behind the [1:16] algorithms but also how to code those [1:19] algorithms and how to deploy those [1:22] algorithms on a physical uh robotic [1:24] platform. In particular, you will learn [1:27] how to use the so-called robot operating [1:29] system which is a sort of operating [1:32] system specifically for robots. And [1:35] finally you will learn how to um uh [1:39] deise new methods and tools for robot [1:43] autonomy. But in partic but first of all [1:46] what do we mean exactly by robot [1:48] autonomy? The idea of automating a [1:51] process is certainly not new. And in [1:55] particular, for example, in the [1:56] manufacturing uh domain, robots has been [2:00] widely used uh throughout the past few [2:04] decades, for example, to assemble uh [2:06] cars. So I'm uh originally from Italy. [2:10] So here I'm showing a Fiat 500 uh being [2:14] assembled by a number of robots. [2:17] So this is amazing. But I refer to this [2:20] application of robotics as automation in [2:24] that every possible situation that the [2:27] robot can uh face during deployment can [2:31] be foreseen at the design stage. So [2:34] basically all the uh motions are [2:38] pre-programmed at the design stage by an [2:41] engineer. So there are no surprises for [2:43] the robots. This is different from the [2:45] field of autonomy whereby a robot needs [2:49] to deal with the scenarios that cannot [2:51] be foreseen at the design stage. Think [2:54] of a self-driving car that has to uh [2:57] enact [2:59] um emergency avoidance maneuver in order [3:01] to avoid a key that is suddenly crossing [3:04] the road. Maybe because the kid is [3:06] changing a duck. How you can foresee [3:09] that as you are designing the robot [3:11] itself. [3:13] This means that uh robots in order to be [3:16] autonomous need to have some capability [3:19] of reasoning. [3:21] Now autonomy as a field is growing [3:23] exponentially. Here I'm just showing [3:25] some of the application of robot [3:28] autonomy. One of the application that is [3:30] currently attracting [3:33] a lot of attention is the application in [3:36] the context of autonomous driving. So [3:38] cars that can drive by themselves. But [3:41] there are many others. For example, [3:42] people are working on unmanned aircraft [3:45] that can deliver uh packages, goods. Uh [3:48] here I'm depicting um a platform from [3:51] Amazon uh flying self drivinging cars. [3:55] Uh for example uh uh this is a prototype [3:59] from Airbus or small uh autonomous [4:03] delivery vehicles again to uh deliver [4:06] goods [4:08] or in not in the context of mobile [4:10] robotics for example surgical robots [4:12] that can perform surgical procedures in [4:16] an autonomous way. Surgical robots are [4:18] currently uh widely deployed throughout [4:21] the world but almost if not all of the [4:24] procedures are under teleoper operation [4:26] from the surgeon. The next logical step [4:29] is for the robot itself to be able to [4:31] perform procedures with a limited degree [4:34] of supervision from a surgeon. [4:38] Now of course and there also application [4:40] in the context of aerospace. Uh part of [4:42] my research is indeed in the context of [4:45] aerospace robotics. uh before joining [4:48] Stanford I was a roboticist at the NAZA [4:51] JPL h where I was working in the [4:53] decision making and AI group within the [4:56] robotics section doing a lot of cool [4:58] work in the field of autonomy for space. [5:02] Now how do we endow a robot with the [5:05] capability of making decisions on their [5:07] own or in other words how do we [5:09] architect the autonomy stack of a robot? [5:11] Well there are many there are different [5:13] ways of architecting the autonomy stack. [5:16] uh for the sake of this class we will [5:18] look at uh a specific one but indeed the [5:21] most popular one referred to as the see [5:24] think act cycle which basically entails [5:27] four main capabilities. [5:31] So the robot first of all has to sense [5:33] the environment by using a variety of [5:37] different sensors, camera, laser based [5:39] sensors, uh radar and so on and so [5:42] forth. [5:44] And based on the sensor readings, it has [5:47] to extract some information. [5:50] Do I see a person in an image? Do I see [5:54] a ball? Do I see a tree? and so on. This [5:58] is the so-cal robot perception module [6:02] based on perceptual information. Then [6:04] the localization and map building module [6:07] tries to localize the robot within a [6:09] map. The map may be known or maybe not [6:13] known and actually the robot has to [6:16] simultaneously localize itself and build [6:19] a map within which it is localizing [6:21] itself. Now that the robot knows where [6:24] it is in the world, then it has to [6:26] decide what to do next. That's the [6:29] decision making uh module. For example, [6:31] in the context of autonomous driving, [6:33] the robot has to decide should I switch [6:36] lane? Should I overcome a car and so on [6:38] and so forth. Once the robot decides [6:41] what to do, usually taking into account [6:44] uncertainties both about the environment [6:47] but also the surrounding agents. Think [6:49] of autonomous car negotiating its [6:51] behavior with the human-driven vehicle. [6:53] Then it has to enact that decision. [6:56] That's the trajectory optimization and [6:58] control module whereby the highle [7:00] decision is translated into a trajectory [7:03] that the robot has to uh follow. [7:06] Once uh the robot then executes an [7:10] action in order to follow a desired [7:12] trajectory, the robot in a way another [7:15] is going to affect the environment and [7:17] the cycle repeats. [7:19] So this is the so-called uh see think [7:22] act uh cycle that entails four main [7:25] capabilities accordingly. This class is [7:28] structured around uh four main modules. [7:31] The third module, the first module [7:33] covers motion planning and um control. [7:37] The second module covers robotic [7:40] perception. The third modules covers [7:42] localization and slum. And the fourth [7:45] module covers the uh decision making, [7:48] state machines and a glimpse into [7:50] reinforcement learning for uh robotics. [7:53] As I said, you will learn both the [7:55] mathematics behind the algorithms, but [7:57] also how to code these algorithms within [7:59] the robot operating system. The course [8:02] is very interdicciplinary. [8:04] Uh we're going to um [8:08] cover a number of topics from very [8:11] different fields which is a strength [8:14] because you become knowledgeable about [8:15] the full autonomy stack. In my career, I [8:18] often found that uh people tend to be uh [8:22] experts in a particular domain but lack [8:25] understanding about all the other [8:26] domains. Robotics by itself is an [8:28] interdicciplinary field and not having [8:31] at least some foundational knowledge [8:33] about all the different components of [8:36] the autonomous tech uh is going to um [8:40] hinder you as you become a roboticist. [8:44] This is however also a challenge. Uh [8:47] you're going to be your mathematical [8:49] skills are going to be stretched. Your [8:51] programming skills are going to be [8:52] stretch. So this class is not going to [8:54] be easy. It's going to be quite complex [8:57] from a mathematical standpoint and it's [8:59] going to be quite complex from a [9:00] programming standpoint. In particular, [9:02] since this class will entail uh the [9:05] deployment of the software that you [9:07] incrementally build throughout the [9:08] quarter on a real platform, necessarily [9:12] you will have to experience the pain [9:14] that every roboticist experiences, which [9:16] is to deal with the hardware. So be [9:18] prepared to spend countless hours [9:21] debugging your code, spending countless [9:23] hour trying to understand why your [9:25] machine is not working. Of course myself [9:28] and the CAS will be here to help but you [9:30] should be aware very aware that uh in to [9:35] some degree you will experience some [9:37] frustration and frustration is in the [9:39] DNA of every roboticist. So if um uh you [9:45] in a way are not willing to embrace this [9:47] pain probably this is not a class for [9:49] you. Second of all, this class as also [9:53] listed on um coursework uh has a number [9:57] of requirements again due to its [10:00] interdicciplinarity. [10:01] There is a requirement in terms of [10:03] programming, a requirement in terms of [10:05] calculus and linear algebra and a [10:07] requirement in terms of probability [10:09] theory and statistics. [10:12] Make sure that these requirements are [10:15] fulfilled. If you are not comfortable [10:19] with one or more of these topics, [10:23] probably you should consider take these [10:24] classes first and then take this class [10:26] next year. [10:28] In particular, uh the CAS won't help you [10:32] with explaining basic concepts such as [10:35] values or basic Python programming. Uh [10:38] we assume that you have that knowledge. [10:39] So as I said, if you feel that you don't [10:41] have that knowledge, just consider [10:43] taking this class next year. We will [10:46] circulate later this week a quiz uh that [10:49] you can take at your pace. It's not [10:51] going to be graded just to self assess [10:54] whether you have the basic foundational [10:56] knowledge to take this class. I don't [10:57] want to scare you. It's just uh I want [11:00] to make you aware of this class will [11:02] entail. [11:04] the grading uh 15% of the grade will be [11:06] from uh a midterm in October 15% of the [11:10] grade from a midterm in November 15% [11:12] from the final project 40% from the [11:14] homework will have a four uh problem [11:16] sets 50% from the sections basically we [11:20] will check that you attend uh uh each [11:23] section uh every week a section one [11:25] section every week and finally extra 5% [11:28] bonus point for either very insightful [11:30] questions on patza or whether you reply [11:34] on patia with an insightful answer and [11:37] the CA and myself will decide what [11:39] insightful means. So it's at our discret [11:42] discretion [11:43] as I said the uh final project will [11:46] entail deploying the autonomy stack that [11:48] you will be that you will incrementally [11:50] build throughout the quarter on a [11:52] platform in particular this platform [11:57] which is also depicted here. So the deal [12:00] of this platform is to have a set of [12:02] sensor that represent [12:04] um that is representative of what you [12:06] will find for example on a self driving [12:08] car. So a laser sensor on top then you [12:11] have a camera you have [12:15] a a beefy processor in order to do [12:18] everything on board. So all the four [12:20] modules so perception localization and [12:23] so on are going to be run on board the [12:24] robots and the robot will need to [12:26] accomplish a task. For example, last [12:28] year the task was to uh um autonomously [12:32] drive in a mock urban environment [12:35] reasoning about for example traffic [12:37] signs which means first you have to [12:38] detect it. Second you have to place it [12:41] uh in a metric map third you had to [12:44] understand this is a stop sign it's not [12:45] a speed limit sign and then you have to [12:47] act accordingly and then we had a sort [12:50] of final competition among the projects. [12:53] So we will be disclosing the details of [12:54] the project for this year later on in [12:56] this quarter. [12:59] Now I'm instructor from the class. This [13:01] class has a five CAS that I'm going to [13:03] introduce. So they're going to be your [13:05] best friends for this quarter. So treat [13:07] them well. Uh you will be interacting [13:10] with them a lot. We're also going to [13:12] collaborate with uh uh some other people [13:16] that I will introduce later on in this [13:17] course. And in terms of labs uh we are [13:20] leveraging uh infrastructure from my lab [13:22] the autonomous systems lab and from a [13:24] lab at the kodak the center for [13:26] automotive research at Stanford. [13:29] The syllabus is provided uh on the class [13:33] website but as I said roughly um the [13:38] course is going to cover uh four modules [13:41] of roughly equal length. uh we're going [13:44] to first cover the topic of trajectory [13:46] optimization and motion planning. Then [13:48] we move into the topic of robot [13:50] perception. So we're going to cover uh [13:52] cameras, camera models, how we extract [13:55] information from image sensors um uh [13:59] both in terms of basic information like [14:02] edges, corners and more advanced [14:04] information. Is there a human or is [14:06] there a cat in an image? Then we move to [14:09] the topic of localization and mapping [14:12] where we have to first provide some [14:14] background in terms of uh probability [14:17] theory and in particular filtering [14:19] theory and then apply that theory uh to [14:21] the problem of localization mapping uh [14:24] through the um tools of common filtering [14:28] and particle filtering. We will then [14:31] move to the uh decision making module uh [14:34] discussing uh uh state machines and then [14:37] how to reason under uncertainty for a [14:40] robot. [14:43] All right. So any questions? [14:46] Yeah. [14:47] >> Do you plan to increase enrollment at [14:49] all? [14:49] >> No. The reason why I cannot increase the [14:52] enrollment is that uh uh we have 30 [14:55] robots and you're going to be grouped in [14:58] group of four people and uh uh currently [15:01] we don't have capacity to have more [15:02] robots. [15:06] >> Since this is the first year the class [15:08] has been split into two pieces A and B [15:10] would like to speak a little about [15:11] what's going to be the transition. [15:13] >> Yes. Yeah. So that's a very good [15:15] question. So this is a um a first in a [15:19] two-part series on robot autonomy. In [15:22] the winter I will be co-eing uh along [15:24] with professor Dorsa Sadik and Janette B [15:28] and um principal robot autonomy 2 which [15:31] is basically the advanced version of [15:32] this class. Principal robot autonomy 2 [15:35] will uh again comprise four main [15:38] modules. The first one will be on [15:41] learning based control and perception. [15:45] Very little here is based on learning [15:47] techniques. These are like more [15:48] classical techniques. The first module [15:51] will actually focus on learning based [15:52] techniques from control and perception. [15:54] The second one will be uh uh f will be [15:57] focused on uh verification and [15:59] validation for autonomous systems and [16:01] different way of architecting the [16:03] autonomous tech beyond the cync act [16:06] paradigm. The third module is uh models [16:09] and algorithms to interact with humans. [16:13] So intent modeling algorithms and so on. [16:15] And the fourth module will uh cover the [16:19] topic of mobile manipulation. [16:22] The uh concept of the class will be very [16:24] similar. We will have assignments [16:27] whereby you incrementally build an [16:29] autonomous stack on top of the one that [16:31] you have built in this quarter. [16:35] showcasing the more advanced [16:36] capabilities like manipulating objects [16:38] in the environment, interacting with [16:40] humans and so on and so forth. I would [16:42] also like to mention that um on Fridays [16:46] I run together with Janet Bogotics [16:49] seminar. So I would encourage you to [16:51] sign up for that robotic seminar. It's [16:53] just a one unitit course. [16:55] um [16:57] is a good way to uh um be updated with [17:01] uh current research topics in robotics. [17:05] One more thing actually so this class is [17:07] offered both as a three and four uh [17:09] credit. The four credit options is [17:12] identical to the three credit option. [17:13] The main difference is that you will be [17:15] asked toward the end of the quarter to [17:18] review um a paper focused on robot [17:22] autonomy. There was some other questions [17:24] over there. [17:26] >> Yeah. [17:27] >> I was just curious in comparison to the [17:29] single quarter class last year, is this [17:32] equivalent to the 274 from last year or [17:34] was it split up into this quarter and [17:36] next quarter? [17:37] >> No. Uh [17:39] so it's it's similar but it's not [17:42] equivalent. So in particular um [17:46] the course as I taught it in the three [17:48] previous years was extremely packed. So [17:51] this year what I did was to unpack it a [17:54] little bit and in particular remove the [17:56] part focusing on um machine learning [18:00] tools to the advanced version. So for [18:02] example in this uh 274A so this quarter [18:06] we won't have uh for the for the large [18:08] part uh machine we won't cover machine [18:11] learning techniques. [18:12] On the other hand, I've included an [18:14] additional lecture on Fridays to provide [18:17] more advanced material that provides me [18:19] with an opportunity to go more into the [18:22] details of some topics whereby in the [18:25] previous version where I had to do [18:26] everything in one quarter, some of the [18:28] details were a little bit rushed. So [18:31] main difference is that uh more details [18:33] because we have one lecture one [18:35] additional lecture per quarter and some [18:38] material has been moved to um um the [18:42] winter quarter and some additional [18:44] material has been included in particular [18:47] now we have a week where we focus on [18:50] multi-ensor perception so how to fuse [18:52] information from multiple sensors that's [18:53] not something we had last year and also [18:56] a couple of lectures on um open source [18:58] projects for uh uh software for [19:02] autonomous systems. So it turns out that [19:04] there are open source projects whereby [19:07] uh people are collectively contributing [19:09] to the autonomous stack for self-driving [19:11] cars and these systems are actually [19:13] getting traction in industry. So I want [19:15] to expose you at least at high level uh [19:20] to those tools. [19:23] >> Yep. So, uh, if you're signed up for [19:25] this class as either CS237A or EE260A, [19:29] you can also go to the Friday lectures. [19:31] >> Yes. Yeah. If you are in a 200, uh, [19:34] version of the class, regardless of [19:35] being AA, E, or CS, you should go to the [19:38] Friday lecture. The only listing whereby [19:41] you don't have to go to the Friday [19:42] lecture is if you are sign up for AA [19:45] 174. [19:47] >> Are the midterms in class? [19:49] >> The midterms are in class. If uh the [19:51] time does not uh work for you then we [19:54] can find an alternate time but by [19:56] default the midterms are going to be in [19:58] class. [19:59] >> I see that the weightless numbers are [20:01] different for E26 and E [20:06] because of the same. [20:10] >> Yeah. So the way the registar office [20:12] works is still a little bit mystery to [20:14] me but I believe that there is an [20:16] overall uh waiting list where they're [20:18] all pulled together and the right [20:20] priorities is given to each student but [20:22] basically if you you can join one of the [20:25] four waiting list with underlying idea [20:27] that there is a common waiting list at [20:28] the end. [20:30] Why is that in that way that is beyond [20:32] my uh knowledge [20:36] other questions? [20:38] All right. So we can start with the [20:40] first topic which is the topic of mobile [20:44] robots kinematics. [20:46] The first module as I said is going to [20:48] cover control and planning. But to do [20:51] controller planning you need a model. [20:53] And in particular in this class we're [20:55] going to focus primarily on uh mobile [20:58] systems which cover a large class of [21:01] autonomous systems. Not all of them. For [21:03] example, a surgical robot is in general [21:06] not mobile, meaning that the base is [21:08] fixed. But many autonomous systems we [21:11] care about like for example self-driving [21:13] cars, airplane unmanned airplanes and so [21:16] on uh move around. [21:19] So to control the motion of such [21:21] systems, we need to learn a model for [21:24] their dynamic evolution. In particular, [21:27] we have to learn the constraints that [21:29] their dynamical evolution has to uh [21:32] obey. [21:33] For example, as a driver, you know that [21:36] as you drive your car, uh you cannot [21:38] move sideways, but you know that by [21:40] concatenating a number of maneuvers, at [21:43] least if there are no obstacles, you can [21:45] go anywhere you want. So, this is an [21:47] example of a constraint on your on your [21:50] motion. You cannot drive uh sideways but [21:52] by being clever in how you concatenate [21:55] your backward and forward maneuver you [21:58] can go anywhere you want. We want to be [21:59] able to have model that allow us to [22:01] perform the type of reasoning [22:05] accordingly. Uh let's talk a little bit [22:08] about the uh constraints that a robot [22:11] has to deal with in order to plan its [22:14] trajectory. And in particular let's [22:17] start from the basics. So in this class [22:20] and in general uh a robot is going to be [22:24] uh defined by a set of generalized [22:26] coordinates referred here as xi. The set [22:30] of generalized coordinates is the [22:32] minimum set of coordinates that allow [22:34] you to uh specify the pose of a robot. [22:40] Like for example in the case of [22:43] a wheelid robots whereby you just have [22:48] one wheel [22:52] that is rolling on the plane with a [22:55] sagittital plane that is orthogonal to [22:57] the plane. The sigital plane is the [22:59] plane that contains the wheel. [23:02] So the let's denote with XY the center [23:07] of the wheel and with the theta the [23:10] heading of the wheel we respect to some [23:14] reference system. Of course it's an [23:17] ideal uh robot a wheel itself is not [23:20] statically stable. So it would tip hover [23:22] but let's assume that we are in a world [23:23] where a wheel can stay perfectly in [23:26] balance. [23:27] So the configuration space for uh this [23:30] robot will be the xy position of the [23:34] center of the disk and the heading angle [23:37] theta. So in this case the configuration [23:39] page will be uh threedimensional. [23:43] The motion of the system or the [23:45] trajectory is simply the time evolution [23:48] of the configuration variables. So [23:50] basically the function that maps t into [23:56] the configuration variables and we [23:57] assume that we have n of them. In the [23:59] case of the unicycle we have three. [24:02] Now the motion of uh the uh the robot [24:06] can be constrained in a number of ways. [24:08] H typical way it can be constrained is [24:11] through uh so-cal constraints. These are [24:15] constraints that only involve the um [24:18] configuration variables but not its [24:20] derivatives. In particular are [24:22] constraints of the type hi [24:25] s= z for i = 1 dot k. So we can have a [24:31] number of uh these constraints. [24:35] Now the effect of these constraints is [24:37] to effectively reduce the accessible [24:40] space for the uh robot [24:43] and in particular to reduce the [24:45] accessible configuration to level set of [24:48] the functions hois. [24:52] Now how do this constraint arise? These [24:55] constraints usually arise due to uh [24:57] mechanical connections. Think for [24:59] example of [25:01] um a manipulator with a prismatic joint [25:05] and some revolute joints. [25:08] These con these uh joints reduce the [25:12] degrees of freedom of the robot and [25:14] accordingly reduce the number of [25:16] generalized coordinates that are needed [25:18] to describe the position of the uh [25:21] robot. More concretely, suppose that uh [25:27] you have a manipulator with uh [25:33] that comprises two pieces which are [25:36] connected through [25:40] a revolute joint. So a joint that allows [25:42] them to rotate with respect to each [25:44] other. So each piece is a rigid body in [25:48] the plane. So each piece can be [25:49] described by three configuration [25:52] variables. Say for piece so this is [25:55] piece number one and this is piece [25:56] number two. So for piece number one [25:59] let's the uh coordin coordinates of this [26:03] point given by x1 and y1 and let's the [26:06] heading [26:08] be denoted as theta 1. For the second [26:11] piece, let's the coordinate of this [26:13] point be denoted as x2 y2 and the [26:19] heading be denoted as theta 2. So what [26:24] are the uh holomic constraints induced [26:26] by the revolute joint meaning induced by [26:29] the fact that these two uh pieces are [26:32] joined together. [26:36] >> Yep. [26:36] >> X1 [snorts] and X2 have to be the same. [26:38] >> Yep. X1= X2 [26:41] and the Y1 is equal to Y2. [26:45] So this will be the H1 function. This [26:47] will be the H2 uh function. [26:51] So accordingly the configuration space [26:54] theoretically is six dimensional. Three [26:56] degrees of freedom from here, three [26:58] degrees of freedom from there. But we [27:00] have a two constraints [27:03] which reduce by two the space of uh the [27:07] accessible space accordingly. How many [27:10] configuration variables do you think we [27:12] need to fully describe the pose of the [27:14] system? [27:16] >> Four six the region number of [27:18] configuration variables minus the number [27:20] of alonomic constraints. In particular, [27:22] the reduced set of configuration [27:23] variables could be X1 with one theta 1 [27:26] and then the um relative angle between [27:31] the first piece and the second piece. So [27:34] basically the joint [clears throat] [27:35] angle joint angles are typically [27:39] a reduced set of coordinates for [27:41] manipulators that have a prismatic and [27:43] revolute joints. Does it make sense? [27:47] Now this is fairly straightforward. The [27:50] second uh class of constraints and these [27:53] are really the constraints that are very [27:54] important for uh for us is uh the class [27:58] of kinematic constraints. These are [28:00] constraint that involve not only the [28:02] generalized coordinates but also the [28:04] time derivative of the generalized [28:06] coordinates. In this class the dot [28:10] so dot [28:12] uh denotes the derivative with respect [28:14] to time. [28:16] Okay. So, kinematic constraints are [28:19] constraints that entail not only the [28:22] generalized constraints but also the [28:24] time derivative the generalized [28:25] coordinates but also the time derivative [28:27] of the generalized coordinates. [28:30] These constraints [28:32] constrain the instantaneous admissible [28:34] motion of the mechanical system. [28:36] Basically constrain the velocity vector [28:38] of the mechanical system. For example, [28:41] in the case of um uh your car, you [28:45] cannot move sideways. [28:48] Now these constraints are often time [28:51] represented in the fium form which means [28:54] that they're linear in the generalized [28:57] velocity. [28:59] So the dependency on the generalized [29:03] coordinate can be nonlinear but the [29:04] dependency on the generalized [29:07] velocities. So the time derivative of [29:08] the generalized coordinates has to be [29:11] linear. We'll see a few examples later. [29:15] Now if you have anomic constraint you [29:18] can certainly um uh reduce it to a [29:23] kinematic constraint but just taking a [29:26] time derivative of it. In particular, [29:28] the derivative with respect to time of h [29:30] of i by the [29:34] uh classical theorem from calculus is [29:37] equal to the derivative of h of i with [29:39] resp to times the derivative of s with [29:41] resp to time. [29:46] So [29:47] um an aonomic constraint implied implies [29:52] a kinematic constraint trivially in [29:54] particular in platium form whereby the [29:56] dependency on the 10 derivative of the [29:59] generalized coordinates is linear. [30:02] The question is is it true that if you [30:05] have a kinematic constraint in [30:08] particular in fium form. [30:14] So assume that you have a constraint a [30:17] transpose [30:19] uh s dot equal to zero. Is it true that [30:24] there there always exist [30:28] uh a function h such that the time [30:32] derivative of [30:35] h with respect to time gives rise to the [30:39] constraint a transpose s [30:42] dot equals z. [30:46] So we saw that if there is anomic [30:47] constraint I can take the time [30:49] derivative and obtain a kinematic [30:51] constraint. But if I give you kinematic [30:53] constraint, is it always true that I can [30:55] find a function h such that if I take [30:57] the time derivative, I obtain the [30:59] kinematical constraint [31:04] any guesses? [31:09] >> Does h also have to equal zero? [31:11] >> Yeah, it's anomic constraint. So a the [31:13] reason why the constraint imply a [31:15] kinematic constraints is that h is equal [31:17] to zero. So the derivative of zero with [31:19] respect to time is zero. And then here [31:22] you just do the compositional [31:23] derivatives. [31:27] >> Seems like you're gonna integrate that [31:28] function. But [31:30] >> yeah, in an integr integraability [31:32] problem. [31:32] >> Yeah. Unless the function is very weird, [31:35] most nice functions are inable, right? [31:37] [snorts] [31:38] >> Well, yeah, it's a bit more complicated [31:40] than that. But the short answer is that [31:42] no. in general uh for arbitrary and [31:47] we'll see some examples and we'll see [31:48] the physical interpretation of why [31:50] integraability might not hold. There are [31:52] kinematic constraints that cannot be [31:54] integrated out into holomic constraints. [31:57] Constraints that cannot kinematic [31:59] constraints that cannot be integrated [32:01] into holomic constraints are referred to [32:03] as nonholomic [32:05] uh constraints [32:07] and they affect the kinematic of a robot [32:10] in a completely different way where to a [32:12] holomic constraint. And to make this [32:14] point clear uh let's consider the simple [32:17] case whereby we have a single [32:21] kinematic constraint in uh prof. [32:27] So we have a transpose of i [32:30] dot equal zero and we have two cases. [32:33] Case number one we can find [32:37] we can find [32:40] h [32:42] uh such that h equals z such that the [32:46] time derivative of h with resp to time [32:50] gives the kinematic constraint. [32:55] So this is the situation where we can [32:56] integrate out the kinematic constraint. [32:59] If this is the case, what this [33:00] constraint is saying is that we have a [33:03] loss of accessibility. [33:05] So the space the configuration of space [33:08] is limited. We can only operate within a [33:11] level set of the function h. So a [33:14] holomic constraint from a physical [33:17] intuition standpoint implies that the [33:20] motion is constrained to a n minus one [33:23] dimension [33:25] uh space of the whole configuration [33:27] space. So for example if you have a [33:31] configuration space that is two [33:32] dimensional with variables x1 and x2 and [33:35] your allomic constraint says that x1 [33:38] plus x2 is equal to zero. It means that [33:40] you can only move on the line as opposed [33:42] to the entire plane. [33:44] With nonolomic constraint actually the [33:46] situation is different. The nonallomic [33:50] constraint constrain the velocities that [33:52] you can enact at each specific [33:55] configuration. [33:59] So here we cannot integrate out. You [34:02] cannot integrate out [34:08] which implies that the velocities are [34:10] constraints. [34:21] So this means that at each specific [34:23] configuration not all velocities are [34:26] admissible. [34:28] But this constraint does say nothing [34:30] about uh uh actually does not constraint [34:34] at all the possible regions of the [34:36] configuration space that it can reach. [34:38] Let me give you an example to make this [34:39] clear. So if you're driving [snorts] a [34:41] car at a given position, the velocity [34:47] that uh is in the direction that is [34:49] sideways with respect to the [34:50] longitudinal axis of the car is not [34:53] permitted. So you cannot move sideways [34:56] but you can reach any point uh in the [35:00] computational space. So basically in the [35:02] plane by concatenating different [35:03] maneuvers that's basically an [35:05] incarnation of a nonomonomic constraint. [35:08] So the way it's completely different is [35:10] that with the nonolomic constraints you [35:12] constrain the velocities but not the [35:15] accessible portion of the configuration [35:17] space. With holomic constraints you [35:19] constrain the accessible portion of the [35:22] uh accessible space. [35:25] Make sense? [35:31] I give you let me give you a more [35:32] interesting example to makes this even [35:34] clearer. [35:37] In this class, we will mostly consider [35:40] wheel vehicles. So I want to give an [35:43] example of a wheel system and in [35:45] particular going to go back to the [35:47] unique cycle system. So a system whereby [35:49] we only have one wheel that is rolling [35:51] on the plane. [35:53] So the drawing was as follow was as [35:56] follow. So we have XY this is our [35:58] reference system. Uh we have a a wheel [36:03] that is rotating on a plane. The wheel [36:05] is constrained to lie on the sagittital [36:07] axis and the sagittal axis is orthogonal [36:11] to the plane. So think of a coin that is [36:13] just rolling on its edge. [36:17] So the configuration as we said before [36:20] is xy theta where xy is xy position of [36:24] the center of the wheel and theta is the [36:26] hanging of the wheel. [36:32] So let's assume that this uh uh wheel or [36:35] disc rolls without slipping. What does [36:38] that mean? Rolling without slipping or [36:40] pure rolling entails that the velocity [36:43] of the contact point has a zero [36:46] component that is um in the direction [36:50] orthogonal to the sagittital plane. So [36:53] basically if this is the direction that [36:56] is orthogonal to the sittal plane the [36:59] velocity vector [37:02] has to form a 90° angle. So basically [37:06] saying that you cannot move sideways. [37:08] Rolling without slipping means that your [37:10] coin cannot move sideways which again [37:12] means that the velocity the contact [37:14] point cannot have a component that is [37:16] orthogonal to the sigital plane. [37:18] So how do we translate this condition [37:21] into uh a mathematical constraint? [37:26] Well, [37:28] uh [37:30] yeah. So, [37:35] let this arrow denote the uh velocity [37:38] vector of the contact point and let by [37:41] EV [37:43] denote the unit vector in the direction [37:47] of the velocity of the contact point. [37:49] Yeah. data [37:51] point is [37:53] >> no is um so is the heading of the coin. [37:59] So this vector is lying on the plane. [38:02] The coin is always orthogonal to the [38:04] plane. So think of a wheel. So think of [38:09] a coin. So this will be the coin. Theta [38:12] is the angle between the face and say [38:14] this reference axis. Yeah. Not that [38:17] representing. Oh, here I did I think a [38:20] better job maybe in representing a 3D in [38:24] 2D. So this would be theta. Make sense? [38:28] So how do we translate the side the um [38:32] size ellipse constraint into a [38:33] mathematical form? Let EV be the unit [38:36] vector in the direction of the um [38:40] velocity vector of the contact point. [38:42] So what are the coordinates of EV in [38:46] terms of theta? [38:50] So the x coordinate [38:53] so this coordinate will be what? [38:56] This is a unit vector. So this will be [38:59] e. Unit vector means that the magnitude [39:02] of this vector is equal to one. So the [39:04] length of this segment is equal to one. [39:07] So what's [39:09] >> what's that? cosiness of theta and the [39:12] other one is sinos of theta. [39:17] So let's then define the vector that is [39:22] orthogonal to ev. This symbol means [39:25] orthogonal. [39:27] So the vector that is orthogonal to ev [39:29] will be this vector here. [39:34] So this angle is theta. So this angle is [39:36] pi al minus theta. [39:42] So what is this uh coordinate [39:50] cosine of pi pi / 2 minus theta [39:58] and uh uh since we are now at the bottom [40:02] minus sin of p / 2 minus theta [40:06] which is equal to sine of theta minus [40:11] cosine of theta. [40:14] You can easily verify that two these two [40:17] vectors are orthogonal because if you [40:18] take the dot product you have a cos sin [40:21] cosine of theta * sin of theta minus sin [40:25] of theta cosine of theta which is equal [40:26] to zero. So you can immediately verify [40:29] that these two vector are orthogonal. [40:31] Orthogonal means that EV dotproduct EV [40:38] v orthogonal is equal to zero. [40:42] Okay. [40:44] So basically the no size constraint [40:46] entails that the velocity vector does [40:48] not have a component in a direction that [40:50] is orthogonal to this digital plane [40:52] which mathematically means that the [40:54] vector V whose components are given by X [40:58] dot Y dot [41:01] is orthogonal to EV orthogonal. [41:06] So in other words, [41:13] the pure rolling constraint [41:20] says that [41:22] x dot y dot dotproduct e v or tona is [41:28] equal to zero. This is the mathematical [41:30] way of saying that the velocity vector [41:33] does not have a component in a direction [41:35] that is [41:37] ortho orthogonal to the digital plane. [41:41] So if we take the multiplication this [41:43] means that x dot time sinus of theta [41:46] minus y dot cosinos of theta is equal to [41:49] zero. And that's your uh fing constraint [41:54] for the kinematics of a rolling disc on [41:57] a plane. [41:59] Note that it's a puffion because the [42:01] dependency on the time derivatives of [42:03] the generalized coordinate is linear. [42:05] The dependency on the general coordinate [42:07] itself is nonlinear. In particular here [42:09] is through science and cosiness. Now [42:11] this constraint limits the um um [42:17] admissible motions of the disk basically [42:19] entails this the constraint that we [42:22] cannot move sideways but does not imply [42:24] any loss of accessibility. You can [42:26] easily convince yourself that with such [42:28] a system you can reach every single [42:31] point in the plane by simply considering [42:33] a three-point maneuver. I have an [42:35] initial condition in terms of position [42:36] and heading. I have a final condition in [42:38] terms of position and heading. A simple [42:40] maneuver to join this initial and final [42:42] conditions is to first rotate in place [42:45] in order to intercept the segment toward [42:48] uh the final condition. Move toward your [42:50] final condition and finally rotate in [42:52] place in order to align your heading. [42:54] So this is just a simple proof that this [42:56] system this constraint is not limiting [42:59] accessibility but is limiting accessible [43:02] motions. So that's when you were asking [43:04] about cases whereby you don't have [43:06] integraability that's a case with a [43:08] clear physical interpretation [43:12] will vehicles in general are [43:13] non-holomic. Yeah. [43:14] >> So here there are no constraints on like [43:16] theta dot the ability to to rotate [43:19] >> here. No. Yes. But there could be other [43:21] systems where you wouldn't be able to to [43:23] do that sort of [43:24] >> of course and now and later on that's a [43:27] very good question. We're going to [43:28] refine this system in order to deise [43:30] models that are actually useful. It's [43:32] not useful right to have a model where [43:33] you say that the angular velocity is [43:35] unbounded. Of course that is not [43:36] achievable by any robots. We're going to [43:38] refine this model here. I just want to [43:40] fix the DS of about nonomic constraints. [43:45] Okay. So key point here is that the [43:48] kinematic model of a manipulator in [43:50] general is different from the kinematic [43:52] model of a wed system [43:56] because the first one is primarily [43:57] affected by holomic constraints. The [43:59] second one is primarily affected by [44:01] nonolonomic constraints and discussed uh [44:04] significant differences between the two. [44:07] We talk a lot about wheels. Let me be a [44:09] little bit more specific about wheels. [44:11] So there are many type of wheels. Um the [44:15] two most popular ones are um the uh two [44:19] different incarnations of standard [44:21] wheels. Uh the standard wheels is just a [44:24] wheel as you know whereby the wheel can [44:27] freely rotate around an axis that is [44:31] orthogonal to the sigital plane. Yeah. [44:34] >> On the last slide [44:36] >> um I see how you did the derivation for [44:38] x dot sin theta minus y cosine theta. [44:41] How do you get what's the next step [44:43] to the the vector times ADA dot? [44:49] >> So how do I go from here to here? [44:51] >> Oh yeah, because X dot [44:57] is X Y theta. So X dot So X is XY theta [45:02] X dot is equal to X dot Y theta dot and [45:05] theta dot. So here I had did a zero. So [45:10] if you multiply this vector by side dot [45:13] you obtain exactly this condition simply [45:17] because the last component zero cancels [45:19] out with the multiplication with theta [45:21] dot. The reason why I wrote it in this [45:24] way is because this is the canonical way [45:26] of writing a fing constraint that is in [45:28] the with respect to the full uh vector [45:31] of configuration variables as opposed to [45:33] just a subset x and y. [45:36] Yeah, thanks for noting that. [45:40] So standard wheels as I said are just [45:42] normal wheels whereby the wheel can [45:44] freely rotate around an axis that goes [45:46] through the uh center of the wheel. [45:49] The fixed standard wheel is a wheel [45:53] whereby the wheel cannot rotate around [45:57] the vertical axis. So think about a [46:00] shopping cart. The back wheels usually [46:02] are fixed standard wheels. They can [46:05] rotate around an axis that go through [46:07] the center of the wheel, but they cannot [46:09] rotate around a vertical axis. [46:13] Um, [46:15] the steerable standard wheels are [46:19] identical to the fixed standard wheels, [46:22] but with exception that now these wheels [46:24] can rotate around the vertical axis, [46:26] meaning the axis that goes through the [46:29] center of the wheel and the contact [46:31] point. [46:33] Another interesting type of wheels is [46:35] represented by the caster wheels. These [46:37] are the wheels that are in the front of [46:39] your shopping cart. This the caster [46:42] wheels have one notable difference. In [46:46] particular, the center of the wheel has [46:48] an offset with respect to the attachment [46:50] point of the wheel to the chassis of the [46:52] robots. This implies that the [46:56] [clears throat] uh axis of [46:59] the vertical axis of rotation doesn't go [47:02] through [47:04] the center of the wheel. So why is it [47:07] useful is that this type of wheel can [47:11] align with the lateral movement. So when [47:13] you have a shopping cart and you turn [47:15] your shopping cart, you may have noticed [47:17] how the front wheels align immediately [47:19] with the lateral movement. [47:22] So you have the backer wheel that gives [47:24] you the stability for the cart and the [47:27] front wheels that gives the [47:28] maneuverability for the cart [47:32] and caster wheel as well can be just [47:35] freely steerable or they can be also [47:37] controlled. [47:38] There are additional types of wheels uh [47:42] for example Swedish wheels, [47:44] omnidirectional wheels and so on but for [47:46] the sake of this class these are the [47:47] wheels that we're going to be concerned [47:49] about. [47:51] So it was just a slight detour in the [47:53] world of wheels. [47:57] >> Active means that you can uh control it. [48:00] Passive is like in the shopping cart [48:02] that the wheel uh just align itself with [48:07] the um lateral movement. Active means [48:10] that you have an actuator that actually [48:12] can can turn itself. [48:17] Okay. So back to kinematic models. Now [48:20] we understand that uh [48:23] kinematic constraints are important and [48:26] let's assume that we have a system [48:27] whereby we have a number of kinematic [48:30] constraints. For example, in the case of [48:32] a wheel system in general if you have a [48:35] k wheels uh you will have a kinematic [48:38] constraints one constraint per wheel due [48:41] to the no side sleep uh constraints. So [48:45] let's assume that we have a k of them. [48:48] We can compactly represent these k [48:51] constraints in matrix form in terms of a [48:54] matrix a which is a function of site [48:56] times [48:58] dot. [49:00] Any question about this? So it's same as [49:03] we did before. The only thing is that [49:04] now we're stacking multiple kinematic [49:06] constraints. [49:07] >> Is the top like brand new form always [49:11] possible or is it just a specific type? [49:14] No, it's not always the case that your [49:16] kinematic constraints is in fat form. [49:18] Turns out that for wheels typically in [49:20] same fat form and since in this class [49:21] we're mostly focused on a wheel system [49:24] the constraint that you will see in this [49:25] class will be in fat form. [49:29] As we said uh each um kinematic [49:32] constraint uh provides a constraint of [49:35] admissible velocities and in particular [49:39] if we have a k constraints what that [49:42] implies is that the [49:45] generalized velocity vector has to lie [49:49] in the null space of the constraint [49:51] matrix a transpose. This is what this [49:54] constraint is saying that at a [49:57] configuration xi [49:59] the velocities that are admissible are [50:01] those such that a transport time x dot [50:04] is equal to zero which means that x dot [50:06] has to be in the n [clears throat] space [50:08] or in the kernel of matrix a transpose. [50:11] So there was a question [50:13] yeah [50:14] >> what is a transpose? So a transpose is [50:17] just uh the matrix whereby I have [50:19] stacked all the uh vectors that describe [50:23] the pattern constraint. So for example, [50:27] if I have two pattern constraint, the [50:29] first one is a1 transpose dot equal z. [50:34] For example, in the case of the unic [50:36] cycle, uh a1 will be s of theta minus [50:40] cos theta 0. Then I have a second one a2 [50:44] transpose I do equal zero. For [50:47] conveniency I just define a matrix a [50:49] transpose as a1 transpose a2 transpose [50:54] and instead of collecting a bunch of [50:57] different constraint I just have one [50:58] compact constraint in matrix form a [51:00] transpose equals z. [51:03] So this n is equivalent to this. [51:09] Okay. [51:14] So what is saying then is that the the [51:17] missible velocities are those that lie [51:19] in the n space of matrix a transpose [51:25] which means that how can we represent [51:28] the admissible velocities? [51:30] Well the null space of matrix a [51:33] transpose is going to have a basis. [51:37] For example, if uh the compilation space [51:40] is three dimensional and uh you have [51:44] only one constraint which means that the [51:47] um you have only one row. What is the [51:50] dimension of the kernel? [51:52] >> Two, [51:53] >> right? So in which case what's the [51:54] dimension of the basis? [51:57] >> What's the dimension of the basis for [51:58] the kernel? [52:00] >> Two. Perfect. Yeah. So it means that you [52:02] can describe the kernel uh with the two [52:04] vectors that are linearly independent [52:06] which means that the admissible [52:08] velocities can be represented as the sum [52:12] of the linear combination of the basis [52:15] vectors times some uh scaling factors. [52:19] This is basically linear algebra. We are [52:22] saying that that missible velocities are [52:23] those that line the kernel which means [52:25] that they can be written as a linear [52:27] combination of the basis vectors that [52:29] describe the kernel. So this gives us a [52:32] procedure to deise kinematic models. We [52:35] stack all the constraints. We build the [52:38] constraint matrix. We look at the kernel [52:40] space. We find the basis. The admission [52:42] admissible velocities can be then [52:45] represented as a linear combination of [52:47] the basis vectors. Which basically means [52:49] that now the dynamics of your system are [52:51] simply given by the solution to a [52:54] nonlinear differential equation whereby [52:57] uh your velocity is a linear combination [53:00] of basis vectors time some uh scaling [53:03] factors uj which have an interpretation [53:05] of control inputs. I'm going to give an [53:09] example in a second to make this [53:10] clearer. But this is the general idea. [53:14] Kinematic constraints we put them [53:15] together. We find the constraint matrix. [53:17] We look at the kernel. The kernel is a [53:19] basis. The admissible velocities are [53:22] those that belong to the kernel. Hence, [53:24] they can be described as a superposition [53:26] of basis vectors. That's what gives us [53:29] the kinematic model of the robot. Let's [53:31] come back to the unicycle to make this [53:34] clear. [53:35] We start from the pure rolling con pure [53:39] rolling constraints which I have it [53:41] here. [53:45] So in this case [53:48] we we only have one kinematic [53:51] constraint. [53:53] So a transpose is equal to [53:57] sin of theta [54:00] minus cosine of theta and zero. [54:07] So my matrix a transpose in this case is [54:10] streamly equal to the vector a [54:12] transpose. My matrix is just a row. The [54:14] configuration space is threedimensional [54:17] which means that the kernel space is two [54:19] dimensional which means that the kernel [54:21] uh can be described through two basis [54:24] vectors. [54:25] We're we're free in choosing our basis [54:28] vectors. But a convenient choice is the [54:31] one given here where the f first vector [54:34] is cosine of theta s theta 0 and the [54:37] second vector is 0 01. To convince [54:40] yourselves that these vectors belong to [54:43] the kernel simply multiply a transpose [54:46] with each one of them. If I multiply a [54:48] transpose with cosine of s what obtain [54:51] is [54:54] zero because it's cosine s minus sin [54:56] cosine * 0 and in the second case obtain [54:59] 0 0 plus 0. [55:02] They're obviously linearly independent. [55:04] So they both belong to the kernel space. [55:06] They're linearly independent. So the [55:07] basis [55:09] which means that X dot can be written as [55:15] um a linear combination of the vector G1 [55:18] so this vector here and a vector G2 this [55:21] vector here which gives right to the [55:24] celebrated unicycle model [55:27] [snorts] whereby X dot Y dot and theta [55:29] dot are equal to the first basis vector [55:33] times the first control input plus the [55:35] second basis vector times the second [55:37] control input. In this case, the two [55:40] control inputs have a physical [55:42] interpretation. [55:44] V is the modulus of the velocity of the [55:48] contact point and omega which is equal [55:51] to theta dot is just the angular speed. [55:54] So this model is going to be very useful [55:56] in this class. This is the model [55:57] actually you'll be using to control this [55:59] robot. And the reason why you can do [56:01] that will be clear in a second. Now in [56:05] general as it was pointed out we should [56:07] also account for constraints. So the [56:09] unicycle model can be augmented with [56:11] constraints in terms of maximum uh [56:14] driving speed B and maximum angular [56:17] speed omega. [56:21] So this is interesting so how we can [56:23] from kinematic constraints we have a [56:25] systematic procedure to derive a [56:27] kinematic model. [56:30] Now in this class actually we're going [56:31] to basically deal with only one [56:33] kinematic model but I just wanted to [56:34] give you a framework uh to better [56:37] understand where these kinematic models [56:38] come and I will give you later on today [56:40] a reference whereby [56:44] there is a list of a number of kinematic [56:45] models that are useful for autonomous [56:47] robotics so that if in the future you [56:49] need to control an airplane a car a [56:54] trailer and so on you have directly the [56:56] kinematic model so you don't have to do [56:58] all these derivations. But at least you [56:59] know where this is coming from. [57:02] All right. Any questions here? [57:10] Now the unicycle per se is an ideal [57:14] model of a robot. Of course a coin in [57:17] general is not statically stable. So it [57:19] will tip over. [57:21] But fortunately there is um a system [57:25] that is quite useful in robotics uh [57:28] whose kinematics are basically [57:30] equivalent to the kinematics of a [57:31] unicycle and this system is referred to [57:34] as a differential drive robot. A [57:36] differential drive robot, which is this [57:38] robot and the one that you will be [57:40] working with throughout for the rest of [57:42] this quarter, is a robot whereby you [57:44] have two wheels in the back [57:48] that are fixed wheels and one wheel in [57:51] the front could be, for example, a [57:52] caster wheel that allows for the front [57:54] to align with the lateral movement. This [57:57] is a passive wheel and the two wheels in [57:59] the back are active wheels meaning that [58:02] you control the rotational speed of [58:04] those wheels and in particular you can [58:07] control this wheel uh uh differentially [58:09] meaning that one wheel for example can [58:11] move forward and the other wheel could [58:14] move backward. So if you move one wheel [58:16] forward and the other one backward what [58:18] happens to the robot? [58:20] It's going to rotate. That's exactly [58:22] what this robot would do. That's why [58:23] it's called differential drive because [58:24] you can control these wheels [58:27] differentially. [58:29] Now, how do we u devise a kinematic [58:32] model for this robot? Well, this robot [58:35] has wheels and as we discussed [58:39] uh [58:42] wheels in general have um no side sleep [58:46] condition which gives rise to katic [58:49] constraint. In particular, if you look [58:51] at this wheel and we were to repeat the [58:54] same analysis, we will obtain exactly [58:56] the same constraint for this wheel. [58:59] If we then look at this other wheel, we [59:02] would obtain another kinematic [59:03] constraint. But notice that these two [59:05] wheels are connected to each other [59:08] and through an axis that goes through uh [59:11] the centers of both wheels. So, what do [59:13] you think about these two constraints? [59:15] Are they going to be redundant or we [59:16] need to consider both of them? [59:20] So basically saying that this wheel [59:22] cannot go in a side direction. Does it [59:24] imply that this wheel cannot go in a [59:26] side slip direction? Yes. So in this [59:28] case uh these two constraints are [59:31] actually redundant and can be um merged [59:36] into a single constraint. [59:38] The wheel in the front does not really [59:40] give you any kinematic constraint [59:42] because being a caster wheel it can [59:44] freely align with the lateral movement. [59:45] So you don't have a side sleep [59:46] constraint which means that from a [59:48] kinematic standpoint this robot has the [59:52] same kinematic constraints of a [59:54] unicycle. [59:55] That's why the dynamics of a [59:58] differential drive are remarkably simple [60:02] and indeed equivalent to the dynamic of [60:04] a unicycle. The main difference though [60:06] is that in the unicycle the idea is that [60:08] you can control the driving speed and [60:11] the angular speed. In a differential [60:13] drive, you can only control the [60:15] rotational speed of the two wheels. So [60:18] now to find the full equivalency between [60:21] the differential drive model and the [60:22] kinematic model, we have to understand [60:24] how to relate the rotation of the wheels [60:29] with the driving speeds and the angular [60:32] speed of the unicycle. So let's do that. [60:35] Once we have that, we have a full [60:36] equivalency between the two models. So [60:38] you can plan a trajectory for a [60:41] differential drive by using a kinematic [60:43] model as kinematic model simply the [60:45] kinematic model of unicycle and the [60:47] mappings between the driving speeds for [60:50] the wheels and B and omega here in [60:54] particular. Let's find these mappings. [61:00] >> Yep. [61:03] >> But aren't the max speed constraints [61:05] different? Because you could imagine [61:07] like turning up the rotational max a lot [61:09] on the unicycle but not being able to [61:11] use the equivalent of the textual drive [61:13] while also not allowing to go too fast. [61:16] >> Absolutely. I said the kinematics are [61:18] the same because the kinematic [61:19] constraints is the same but the bounds [61:21] are different in that the bounds on the [61:25] rotational speed on the left L here [61:27] means left and R here means right can [61:30] gives rise to different type of bounds [61:32] for V and omega. Depending on the [61:35] specific bounds, we have a different [61:37] subm models which we're going we're [61:38] going to cover in a second. But first, [61:40] let's find a mapping between [61:43] um the left and right rotational speed [61:46] for the wheels and the V and omega for [61:49] the unicycle model. [61:57] So, [62:00] yep. [62:01] All right. So, [62:08] so these are the [62:10] wheels in the back. [62:14] Plus, of course, there is also the [62:15] caster wheel in front. Now as the uh [62:19] robot is moving along a curved path, [62:24] the robot is rotating and in particular [62:27] is rotating around [62:30] some point that lies along the axis that [62:35] joins the centers of the two wheels. [62:37] This point is usually referred to as the [62:40] instantaneous center of uh rotation ICR [62:44] or instantaneous curvature center. Okay, [62:47] so the robot is moving around this [62:49] instantaneous central rotation. [62:53] Any questions here? Which basically [62:55] means that if you were to keep moving [62:58] with the same velocity vector, it will [63:00] move in a circle with this point as the [63:02] center. [63:05] Now let omega be the instantaneous [63:09] angular velocity angular speed around [63:12] the instantaneous center of rotation. [63:14] Actually let me call it ICR [63:16] instantaneous center of rotation. [63:20] Let's consider the midpoint in between [63:23] the two wheels in the back. So this [63:26] let's not by v the uh speed of the [63:30] midpoint. [63:32] Now and let's denote by r [63:36] the radius of curvature. So the distance [63:40] between the midpoint and its internal [63:42] center of rotation. [63:44] So b is equal is equal to omega r. [63:51] Let's also define l and br [63:56] as the driving speeds for the uh left [64:00] wheel and for the right wheel. [64:10] So for the left wheel we have a v left [64:13] is equal to omega. Of course the angular [64:15] velocity is the same because there is a [64:17] rigid body. So omega [64:21] time r [64:23] minus let's denote this distance as l. [64:28] This is the width of the chassi. [64:31] So r - l / 2 and v right is equal to [64:37] omega r + l / 2. [64:44] So if I take the difference between Br [64:48] and B L, I obtain [64:53] um [64:55] omega L, which means that omega the [65:01] angular speed is equal to the [65:07] differential speed over two. Let's see [65:10] if it makes sense intuition. So if [65:14] um [65:18] VR and VL are equal, [65:22] what's the angular speed? [65:25] Which makes sense because now the robot [65:26] is going straight. If instead uh vr [65:31] L is equal to zero and VR is different [65:34] from zero, then I have an angular speed [65:35] and in particular the robot is rotating [65:37] around the left wheel. [65:40] So this is a mapping between the uh [65:44] driving speed for the right and left [65:46] wheels with omega the angular speed of [65:50] the robot. So we found the first mapping [65:51] relative to the unicycle. We had to find [65:53] the second mapping which is now the [65:55] mapping between V vr VL and V which will [66:00] be the driving speed for the unicycle. [66:02] to find that mapping. [66:05] So as we said we have V [66:08] is equal to [66:11] omega R. [66:13] If I sum V L + V R what I get is V L + V [66:17] R is equal to [66:22] 2 omega R. [66:26] So I can rewrite this as a 2 omega R / [66:29] 2. [66:31] So what I get is that uh the driving [66:34] speed or the midpoint V L + V R is equal [66:38] to [66:40] V L plus VR divided by two which means [66:43] that uh the driving speed is simply the [66:46] average between driving speed between [66:48] driving speed of the midpoint is the [66:49] average the driving speed between the [66:51] left and right wing. [66:53] The mapping is completed by noting that [66:56] V L so the linear velocity for the left [67:01] wheel is equal to omega L * R. r is the [67:06] radius of [67:08] um [67:11] is the radius of the wheel [67:16] and VR [67:19] is equal to omega R * R. So this [67:22] equation, this equation, [67:25] this equation [67:28] and this equation [67:30] provides a mapping between a [67:31] differential drive model and a unicycle [67:34] model and in particular how uh we can [67:37] interpret differential drive robot as a [67:39] unicycle robot whereby we consider [67:42] driving speed and angular velocity with [67:44] respect to the midpoint of the rear [67:46] axis. [67:49] So you can plan by using a unicycle [67:51] model [67:53] and then you can translate well then you [67:56] can compute the angular speeds for the [68:00] left and right wing that gives right [68:02] wing sorry left and right wheels that [68:05] give rise to the desired V and omega by [68:08] using these one to one mappings. [68:13] >> Yep. [68:15] It says we always [68:20] >> Oh yes. Oops. [68:23] Yeah. [68:26] Yeah. Otherwise it makes [clears throat] [68:27] sense dimensionally. Yeah. Sorry. And of [68:31] course [68:33] these mapping are included here. You can [68:36] see exactly now where those mappings [68:38] come from. [68:41] So bottom line is that the kinematic [68:43] models of unicycle also applies to the [68:44] differential drive vehicle with the [68:46] onetoone mappings provided here which [68:48] are the ones that we just arrived. So [68:50] when you will be playing trajectories [68:52] and we will discuss next week how to [68:54] compute trajectories for robots for [68:56] these robots you'll be using a unicycle [68:59] model with the understanding that there [69:00] is a onetoone mapping between the [69:02] driving velocity and the angular [69:04] velocity of the midpoint of the rear [69:05] axis and the angular velocities of the [69:09] rear wheels. [69:11] So now this is a useful model. Yeah. [69:13] Does this model predict any [69:15] singularities like uh suppose the caster [69:18] wheels perpendicular to our range of [69:20] motion and [69:22] >> yeah so this actually goes into the [69:24] definition of the constraints and in [69:26] particular there is a slightly more [69:27] sophisticated model of [69:31] a robot which is referred as a simple [69:33] car model whereby now [69:36] uh we have a two backward wheel as [69:39] before but now we have a two front [69:41] steerable [69:43] And now you might end up in the [69:45] singularities. [69:47] In particular, this model is different [69:49] because now the computation space is [69:51] four dimensional. You have the XY [69:55] position of the midpoint of the rear [69:58] axis, [70:01] the heading of the robot and the [70:04] steering angle. So the angle between the [70:06] front wheels and the longitudinal axis [70:08] of the robot. [70:10] So when you derive the kinematic model [70:12] for this robot now you have to account [70:15] for two constraints and those two [70:16] constraints are not redundant. The side [70:19] no side sleep constraint for the [70:21] backward wheels and the no side sleep [70:24] constraint for the front wheels. So now [70:26] you have two constraints. These are [70:29] slightly more complicated system to [70:30] derive. So it's a but from intuition [70:33] standpoint you have um [70:37] four configuration variables and two non [70:40] redundant constraints which means that [70:42] the new space will be two dimensional [70:46] and that's the model that by doing the [70:48] mathematics you would find the two [70:50] control inputs here are B the speed and [70:55] phi the steering angle of the front [70:57] wheels and the configuration variables [71:00] are XY I and theta [71:03] you have two inputs because the kernel [71:05] is two dimensional [71:06] >> identical to the bicycle right. [71:09] >> Yeah. Yes. [71:11] But [71:12] so this is this is referred to as a [71:14] simple car model depending on how you [71:17] set up the um [71:20] uh the bounds for the inputs. You obtain [71:23] different sub models. In particular, if [71:26] you just have upper bounds on linear [71:29] speed and steering, that's a simple car [71:31] model. Note that here phi is less than [71:34] pi / 2 in order to avoid singularities. [71:38] Uh if [71:40] the steering angle still is upper [71:43] bounded and the velocity can only assume [71:46] the maximum uh forward speed or backward [71:49] speed, the model is referred to as a [71:51] ritz ship car. what is used in motion [71:53] planning. If furthermore the velocity is [71:57] restricted to its maximum value then [72:00] this is referred to as the dubins model [72:02] which you will be using also uh for this [72:05] class also this is quite used. [72:08] Now I'm providing here some additional [72:10] references on how to derive these models [72:13] including discussion about [72:14] singularities. is uh found in this book [72:18] and also an additional reference to [72:20] another book from Steve Laval emotion [72:22] planning where there is a description of [72:24] a fairly large class of kinematic models [72:26] that are useful for robotics. [72:28] >> Why is the steering table not part of [72:29] the configuration? [72:31] >> Last slide from kinematic to dynamic [72:34] models or to better models. So first of [72:36] all as a warning a kinematic state space [72:39] should always be interpreted only as a [72:41] subsystem of a more general dynamic [72:43] model. So similar to your question why [72:45] don't you don't we have x double dots [72:47] and we in terms of accelerations [72:50] often times one reasons in terms of [72:52] kinematic model for trajectory [72:54] optimization because these models are [72:56] simpler uh for optimization purposes and [73:00] then the there is a blackbox module that [73:03] allows you to translate [73:05] uh desire uh kinematic quant quantities [73:08] like for example driving speed and [73:10] angular speed into control signals that [73:14] necessarily have to deal with the [73:16] dynamics. So basically acceleration, [73:18] angular acceleration and so on or so [73:21] that's one way and that's very common. [73:23] Uh another way is actually to improve [73:26] your model by including additional uh [73:30] for example in the unicycle model and [73:33] this is something that we'll be doing in [73:34] the first pet in order to improve the [73:37] fidelity of the model that we use for [73:39] planning and control. We may add an [73:41] integrator and basically add an [73:43] additional making B the velocity a state [73:45] variable and adding an additional [73:47] equation B dot equal A where A now is [73:49] our new control input the uh [73:52] acceleration for the simple car model. [73:54] We could add Z the stealing angle as a [73:57] state variable and then add a new [73:59] control variable Z dot equal U Z which [74:02] will be the uh zero rate. Right? There [74:06] is a tension. On the one hand, you want [74:09] to have a model that is represented [74:11] enough of the dynamics so that when you [74:14] plan a trajectory, the trajectory is [74:15] realizable. On the other hand, you don't [74:18] want to have a model is too complicated [74:20] because trajectory optimization as we [74:22] will see next week is a computation [74:24] intensive process. So if you make your [74:26] model too complex, then it takes too [74:29] long to find a trajectory. [74:32] How to find the right balance is a bit [74:34] of an art in many ways. In this class, [74:36] we're going to discuss how to find the [74:38] right balance for the specific case of a [74:41] wheel system and in particular [74:43] differential drive robots. [74:46] So, this concludes this lecture. The [74:47] next lecture will be devoted to an [74:49] introduction to Ross, the robot [74:51] operating system. On Friday, we'll have, [74:54] if you will, an inspirational lecture [74:56] whereby a friend of mine and a CEO of an [75:00] autonomous truck company is going to [75:02] talk to us about the challenges of [75:04] fielding autonomous systems in the real [75:07] world. Next week, we'll talk about [75:09] trajectory optimization, trajectory, [75:11] tracking, and control. Brett Jones on [75:15] Thursday.