전체 글27 [BOJ 11279] MaxHeap #include using namespace std; void MaxHeapify(int A[], int heap_size, int i) { int left = 2*i; int right = 2*i + 1; int largest; if(left A[i]) largest = left; else largest = i; if(rightA[largest]) largest = right; if(largest != i){ int temp = A[i]; A[i] = A[largest]; A[largest] = temp; MaxHeapify(A, heap_size,largest); } } void BuildMaxHeap(int A[], int heap_size){ for(int i=heap_size/2; i>=1; i.. 2023. 9. 7. Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery [AAAI-19] 1. Contribiution Token Passing(TP)에 SIPPwRT(Safe Interval Path Planning with Reservation Table)을 적용 2. SIPPwRT 2.1 Reservation Table and Safe Interval SIPP : 각각의 dynamic obstacle들의 path를, 시간순으로 정렬된 dynamic obstacle에 차지된 cell들의 리스트로 나타냄 -> 주어진 한 cell의 모든 safe interval을 계산하기 위해 이 리스트들을 모두 interate 해야함 -> 비효율적 Space Time A* : reservation table을 유지하여 주어진 cell의 safe interval 계산을 효율적으로 할 수 있음 2.2 Time.. 2023. 9. 3. [RL-PyTorch] N Step Actor-Critic Mote Carlo : 각 에피소드의 끝에서 학습 Temporal Diffence (TD, Fully online learning) : 매 스텝마다 학습 -> Bootstrapping 적용 시 bias 커질 수 있음 N Step TD : N 스텝 마다 학습 -> Bootstrapping 적용해도 TD보다는 편향이 적음 *Bootstrapping : 예측에 기반해서 또 다른 예측을 수행 -> 예측을 하기 전에 최대한 많은 데이터를 모으는 것이 바람직함 # Multi step Temporal Difference import torch from torch import nn from torch import optim import numpy as np from torch.nn import functional as.. 2023. 9. 2. [RL-PyTorch] Distributed Advantage Actor-Critic (DA2C) [Actor-Critic] loss = $ -log(\pi(a \mid S))\cdot (R-V_{\pi}(S))$ - 일반적인 -log 형태의 loss function과 비슷함 - 차이 : $R-V_{\pi}(S)$ -> 해당 step에서 받은 reward($R$) 에서, 해당 state에서 받을 수 있다고 기대되는 state value 값을(state-action value가 아닌 state value) baseline으로 뺀 다음 loss 를 계산 -> 해당 state 에서 특정 action이 얼마나 효과적이었는지 상대적으로 평가 가능 Actor : policy network -> action을 선택 Critic : State value network -> actor가 선택한 action을 평가함 .. 2023. 9. 1. [Python] Multi processing # Multi processing import multiprocessing as mp import numpy as np def square(x): return np.square(x) x_ = np.arange(72) # print(x_) cpu_n = mp.cpu_count() print(cpu_n) pool = mp.Pool(cpu_n) # CPU 개수와 같은 다중 프로세싱 풀을 만듬 squared = pool.map(square, [x_[3*i:3*i+3] for i in range(cpu_n)]) #Pool의 map method를 활용해 square 함수를 각 배열에 적용 -> 취 print(squared) import multiprocessing as mp import numpy as np def.. 2023. 9. 1. [C++ Data Structure] Stack 구현 #include #include using namespace std; template class Stack{ private: int top_idx, maxSize; T* stack; public: Stack(int max_size) :maxSize(max_size), top_idx(-1) { stack = new T[maxSize]; } bool isFull(){ if(top_idx==maxSize-1) return true; else return false; } bool isEmpty(){ if(top_idx==-1) return true; else return false; } T pop(){ if(isEmpty()) return -1; else return stack[top_idx--]; } void.. 2023. 8. 31. [RL-PyTorch] Policy gradient method, REINFORCE algorithm import numpy as np import torch import gym from matplotlib import pyplot as plt def running_mean(x, N=50): kernel = np.ones(N) conv_len = x.shape[0] - N y = np.zeros(conv_len) for i in range(conv_len): y[i] = kernel @ x[i:i + N] y[i] /= N return y env = gym.make("CartPole-v1", render_mode="human") l1 = 4 # the length of input data = 4 l2 = 150 # dimension of hidden layer = 150 l3 = 2 # output : .. 2023. 8. 28. SIPP: Safe Interval Path Planning for Dynamic Environments [ICRA 2011] 1. Contribution 기존의 MAPF 알고리즘은 Space-time search를 위해 time interval 개념을 사용함 -> 제안하는 Contiguous safe interval의 수는 기존의 time interval의 수보다 훨씬 적음 -> Safe interval을 사용하여 optimality를 보장함과 동시에 search space가 훨씬 작아져 빠른 계산이 가능 2. Algorithm 연속적인 collision free timestep들을 safe interval으로 묶음 각각의 state : (configuration, safe interval) pair로 표현됨 Safe interval : "a contiguous period of time for a configuration, .. 2023. 8. 28. High dimensional object rearrangement for a robot manipulation in highly dense configurations [ISR 2022] 1. Contribution 1. Propose an object rearrangement algorithm that minimizes object movement and grasp targets 2. The algorithm provides safety by considering stackable relationships btw objects and show completeness 2. Problem description goal : Minimize the number of actions that rearrage the objects blocking a target object -> Attempt to find a sequence of the obstacles by using a tree search .. 2023. 8. 24. 이전 1 2 3 다음
