2. Introduction to Autnomous Navigation 2

Autonomous Navigation System

Client & Cloud System

S/W and skill requirements for autonomous driving

the 5 levels of driving automation

Client System

• ROS
• Hardware Platform

Client system in autonomous driving

• Requirements
  • Multiple algorithms are integrated to satisfy real-time and reliability requirements.
  • The processing pipeline must be fast enough to handle the vast amount of data generated by the sensor.
  • Sufficient enough to recover even if an error occurs in any part
  • Strict energy and resource constraints must also be met in processing all of these operations.
• Component
  • operating system
  • Hardware platform

ROS(Robot operating System)

• ROS
  • Powerful distributed computing framework specialized for robotics applications
  • Specific tasks are driven from the node.
  • Nodes communicate with each other through topics and services.
• Problem
  • Reliability: In ROS, there is only one master, and there is no monitor to recover the failed node.
  • Performance: In the process of sending a message in a broadcast manner, the same message may be duplicated multiple times, resulting in a decrease in performance.
  • Security: No authentication and encryption mechanisms.
• responsibility
  • Since there is only one master node, if the master node dies, the entire system dies.
  • This is against the safety requirements of the autonomous driving system.
  • To solve this, a mechanism similar to that of the zookeeper (distributed coordinator) was introduced.
    • When the main master node dies, the backup master node is taken over to operate the system normally.
    • When monitoring through the zookeeper mechanism and detecting a failed node, restart it.

• Performance
  • The communication between the nodes is very frequent, so it must be handled efficiently.
  • Local nodes communicate with each other using a loop-back mechanism, which causes about 20ms of overhead each time.
  • To eliminate this overhead
    • Use shared memory mechanism to process messages to go straight to the destination node without going through the TCP / IP stack
    • ROS node replaces the message communication method from broadcasting to multicast mechanism, greatly reducing the bandwidth consumed by making multiple copies during the broadcasting process.

• security
  • Security problem occurs because there is no symptom and encryption mechanism
    • Because there is no authentication, the node may be down in such a way that it infiltrates the node and continuously allocates memory, exhausting system memory.
    • Since it does not encrypt the messages that are sent and received between nodes, it can be subjected to a man-in-the-middle attack that intercepts them.
  • solution
    • It is solved by using LXC (Linux Container) to limit the amount of allowed resources for each node, and protect the node from the outside through the sandbox mechanism.
    • Encrypt messages sent and received during communication

ROS1 vs ROS2

• Resolving the reliability, performance, and security problems of ROS1 in ROS2
• Changed data processing method (XMLRPS / TCPROS => DDS / RTPS)
• Multi-node is possible in one process (Peer to Peer communication method does not have a separate master and is performed according to the role.)
• Improving reliability and performance through methods such as notifying the master of the polling method based on the parameter, etc.
• Real-time computing (not for performance, but for final decision)
• Enhanced security through DDS (Data Distribution Service) security
• Compatible with various OS, python3 support, various embedded system support etc. https

Hardware Platform

• Example
  • Specifications used by autonomous driving companies
    • Usually use 2 compute boxes (main + backup)
    • Processor: Intel Xeon E5 x (1 pc.)
    • GPU: NvidiaK80 x (4 ~ 8)
    • 5,000W power
    • $ 20,000 ~ $ 30,000 (about 2,000 ~ 30 million won or more)
  • Embedded specification
    • ARM SoC
    • 15W power
    • Localization Pipeline: Processing 25 images per second
    • Deep Learning Pipeline: 2-3 objects per second
    • Planning and control pipeline: route planning within 6ms
    • Driving at about 5 miles per hour (8 km / h)
• Example: Apollo test hardware pack presented by Baidu

Deeplearning on Embeded board

Example

Cloud Platform

Client platform in autonomous driving

• Requirements
  • Because autonomous vehicles are a type of mobile system, a cloud platform that supports them is required.
  • The main functions of the cloud are largely distributed computing (processing, analysis) and distributed storage (storage).
  • Simulation to verify new algorithm
  • HD map production and update
  • Deep Learning Model Learning and Updates
• Required elements
  • Distributed Computing: Spark
  • Heterogeneous Computing: OpenCL
  • In-memory storage: Alluxio

Simulation

• Reasons for simulation
  • Rigorous testing is required before deploying the newly developed algorithm to the vehicle.
  • Testing with a real car is a huge cost and time consuming and safety issue.
  • Mainly tested in a simulator implemented by playing data on ROS nodes
  • It takes a long time to test on one machine, and the test range is not enough.
  • Distributed computing nodes are managed as sparks, and ROS replay instance is driven for each node.(3 hour test running on one server => test in 25 minutes using 8 nodes through a distributed system)

• Opensource
  • Compatible with various platforms
  • There are many methods based on ROS, Unity, Unreal Engine, etc.
  • LGsvl: led by LG
  • Airsim: led by MS
  • Carla: Intel, Toyota led

HD MAP

• HD map creation process
  • Original data processing
  • Point cloud creation
  • Point Cloud Alignment
  • 2D reflection map generation
  • HD Map Labeling
  • Create final map
    • Each step is connected to one job through Spark (In-memory computing mechanism eliminates the need to store intermediate data on the hard disk, greatly improving the performance of the map creation process)

• Evolution of HD map

Deeplearning Model

• Requirements
  • Because autonomous driving systems use a variety of deep learning models, it is necessary to update them to continuously improve the effectiveness and efficiency of the model.
  • It is difficult to quickly learn a model using only one server.
  • Requires a distributed deep learning system based on distributed computing platforms (e.g. Spark) and deep learning frameworks (e.g. paddles) (frameworks such as Tensorflow support them on their own)
  • Requires a parameter server (e.g., Luxi)

• Autonomous driving platform

• Autoware
• Apollo

• Nividia Drive Platform

• Reference SLAM KR 발표 자료

14. Merge sort

Introduction

• Merge Sort is the fastest algorithm we are going to be analyzing. (Fastest on average, quicksort is technically faster, but has the problem of the n^2 worst case). It has a way of dividing the data up like in quick sort, except that it doesn’t require selecting a pivot point to get the nlogn run times.

Why is it Important?

• Merge sort is one of the fastest comparison sorts. It runs at nlogn for all run times, making it reliably fast at splitting up and sorting data.

Lesson Notes

• Merge sort is one of the fastest algorithms for sorting using comparisons. However, this also makes it quite complex as well. It uses the divide and conquer methodology used in the quick sort algorithm.

• It works by dividing up the data in to smaller and smaller chunks. It then recombines them in to a sorted algorithm.

• The array breaks down the data until it is in single unit subarrays. It then recombines them using cursors that only have touch each element once for each combination.

• So each level is going to be at most n amount of “touches”. Because of the way it breaks up the algorithm, it has logn amount of levels.

• This means that is will always run at nlogn timing, as there is no way to break it up worse than logn levels. So it will be n amount of touches per level multiple by logn amount of levels, giving us an even nlogn no matter what array comes in.

• Best Time: Ω(nlogn) : The same algorithm is applied no matter what type of array comes in. This means it will always be nlogn

• Average Time: Θ(nlogn) : The same algorithm is applied no matter what type of array comes in. This means it will always be nlogn

• Worst Time: O(nlogn) The same algorithm is applied no matter what type of array comes in. This means it will always be nlogn

Comparison

Quiz

5. Number System

Number System

• we make use of different kinds of number system to quantify(定量) different objects
• A numbering system is system followed to define a set of values used to measure a quantity.
• with the helping of numbering system we can express the quantitative dimension of any object.
• the computers are extensively used for performing complex calculations and can handle different types of data such as audio, video, images and many more.
• however, for computer this data in any form must be represented only in the form of numbers which a computer can understand and perform different actions as per program instruction
• the computer’s CPU(brain) has been designed to interpret language expressed only by using two states (on or Off). these two states can be best represented by binary number system which makes use of only two numbers(0 and 1 ). therefore, a computer can interpret only binary representation which is a language of 0 and 1.

types of number systems

• there are four basic numbering systems that are used in the human, networking, and computer science worlds.
• the Decimal(데시멀) numbering system we are most familiar which has a base, or radix, of 10 and to us this is natural. why 10? most of us have 10 fingers and that is how it was selected as our numbering systems.

• in mathematics and digital electronics, a binary number is a number expressed using binary numeral notation system or base - 2 numeral system which represents any numeric(0~9) values by using combination of only two possible values that is 0(zero) and 1(one). in digital electronics this is best suited to represent two states ON or OFF.

• hte base-2 number system is a positional notation with a radix(근원) of 2. because of its straightforward implementation in digital electronic circuitry using logic gates. the binary system is used intemally(内部地) by almost all modern computers and computer-based devices.

• therefore, computer is a digital electronic device and the CPU consist of millions of transistor which is fundamental building block for all CPU.

• the decimal numbering system is the most commonly used numbering systems that makes use of 10 digits starting from 0 to 9. any number can be represented by using combinations of any of these 10 numbers.

• a decimal number, or just decimal, refer to any number written in decimal notation, although it is more commonly used to refer to number that have a fractional(很小的) part sepreated from the integer part with a decimal separator.

• in mathematics and computing hexadecimal(also based 16, or hex) is a positional numeral system with a radix, or base of 16. it uses sixteen distinct symbols, most often the symbols 0-9 to represent values zero to nine, and A,B,C,D,E,F(or alternatively a,b,c,d,e,f) to represent values ten to fifteen.

• Hexadecimal numerals are widely used by computer system designers and programmers. as each hexadecimal digit represents four binary digits(bits). it allows a more human-friendly representation of binary-coded values as binary numbers are difficult to read.

4. Computer Systems Architecture

Components of Computer Systems Architecture

• Instruction Set Architecture(ISA): Each CPU implements a specific architecture.
  • an Instruction set is a list of all the program instructions that processor can interpret and execute after fetching the Instruction from the main memory.
  • for this reason, programs compiled for a specific platform can be executed only on the similiar platform for which it has been compiled.
  • the instruction set consists of addressing modes, instructions, native data types, register, memory architecture, interrupt, and exception handling, and external Input/Output.
• Micro Architecture : in computer engineering, micro architecture is a description of the electrical circuitry of a computer, central processing unit that is sufficient for completely describing the operation of the system hardware.(also Referred as computer organization)
  • 즉, 하드웨어 시스템의 운영과 관련
• System Design: it is the process of defining the architecture, components, modules(function), interfaces, and data for a system to satisfy specified requirements.
  • System design could be seen as the application of systems theory to product developement.

• x86은 32bit 운영체제용이고
• x64는 64bit 운영체제용
• 32bit 파일은 64bit운영체제에 호완되지만 반대는 안된다.
• x64 bit 운영체제는 4GB RAM 이상이여야 한다.

4. Analyse time complexity